数据结构与算法实践系列文章（八）散列

散列

散列

目标 ：为了更快的查找 —O(1),拿空间换时间， 计算空间位置更快

定义

“键 -值 对” （key- value pair）的集合

两个关键的问题

• 散列函数 什么是好的散列函数

• 解决冲突 如何进行解决冲突

解决冲突方式

• 开放定址

• 分离链

• 其他（公共溢出）

开放定址

h(x) = x mod 11

x={12,2,17,28,6,23} h(x) = {1,2,6,6,1}

这样以来就有冲突了，这个当冲突时则可以将数据进行往后的坐标点放入 可进行 线性探测，平方探测。。。

分离链

h(x) = x mod 11

x={12,2,17,28,6,23} h(x) = {1,2,6,6,1}

是在这个结点做个链表结点 。单链表的插入删除

C实现

// 开放定址法，删除时时不能真正的删，只能逻辑的删除，让其标记
#include <stdio.h>
#include <stdio.h>
// 标记的状态
enum GridStatus{Active,Removed,Empty};
typedef enum GridStatus Status;
struct HashTable{
    int *key; // key
    Status *status; // 标记的状体
    int size; // 表里的大小
    int remains; // 表中剩余的大小
};
typedef struct HashTable *HT;
HT initHashTable(int size){
    HT h;
    h= (HT) malloc(sizeof(struct HashTable));
    if(!h) return NULL;
    h->size = h->remains =size;
    h->key = (int *)malloc(sizeof(Status)* size);
    if(!h->status){ free(h->key);free(h); return NUll;}
    for(int i=0;i<size;i++){
        h->status[i]=Empty;
    }
    return h;
}
// hash函数
int hash(int x,int p){
    return x%p;
}
int isFull(const HT h){
    return h->remains == 0;
}
// 插入
int insertX(int x, HT h){
    if(isFull(h)) return 0;
    int pos=hash(x,h->size);
    while(h->status[pos] == Active){
        pos = (pos+1) % h -> size;
    }
    h->key[pos] = x;
    h->status[pos] =Active;
    h->remains--;
    return 1;
}
// 查找
int findX(int x,HT h){
  int pos,index;
  index=pos= hash(x,h->size);
  while(h-status[pos]!=Empty){
      if(h->key[pos] == x && h-status[pos] == Active) return pos;
      pos= (pos+1)% h->size; // 循环一圈
      if(pos == index) break;
      return -1;
  }
}
//remove
int removeX(int x, HT h){
    int pos = findX(x,h);
    if(pos==-1) return 0;
    // 只做标记，不修改其中的值，这是绝大部分就是这样的。
    h->status[pos] = Empty; 
}
void printHT(const HT h){
    for(int i=0;i<h-size;i++){
        printf("%4d",i){
    }
    putchar('\n');
    for(int i=0;i<h-size;i++){
        if(h->status[i] == Active) printf("%4d",h->key[i]);
        else if(h->status[i]==Removed) printf("   X");
        else printf("   -");
    }
    putchar('\n');
}
int main(){
    HT h=initHashTable(11);
    insertX(5,h);
    return 0;
}

C++

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
    unordered_set<int> s;
    unordered_map<int, int> m;
    m[101] =33;
    m[-10] = 2233;
    m.inser(pair<int,int>(22,33));
    return 0;
}

Java

Map-->HashMap; 键值对映射
Set--->HashSet;

JAVA中的hashmap是在jdk1.8以前时采用的时数组+链表，jdk1.8以后采用的是数组+链表+红黑树，当元素的个数在8时将链表转为红黑树，所以hashmap的元素的个数在8左右时会将消耗性能。hashMap的初始值元素的个数为16，hashMap的自增因子为0.75，当元素个数为32的时候初始容量为 32/0.75= 。

Python

d = dict() # 字典
d[100] =50