浅析哈希表

但是我们想想为什么会有这种问题？因为我们给每一个单词都分配了一个数组单元，而类似aaaa,zzzz这样的

单词显然是不存在的，因此我们有了一个最常用的哈希化的方法，“取余法”。50000个单词，但我们给它分

配一个容量为100000的数组，我们先将单词转化为10进制数字largeNumber,则 arrayIndex = hugeNumber

% arraySize； 

  哈希化其实是一种压缩，是压缩就必定要付出代价，也就是不能保证每个单词都能有自己的空白数组单元，

这也就是我们所说的“哈希冲突”。我们有两种方法解决冲突，一种是给冲突的数据再找一个空白数组单元，

叫做“开放地址法”，第二种是创建一个存放链表的数组，将所有冲突数据放到对应位置的链表中，这叫做

“链地址法”。

  而开放地址法又有线性探测、二次探测和再哈希法。线性探测比较简单，就是依次向下寻找空白数组单元。

简单写一下线性探测的插入数据的java代码:

public int hashFunc(int key){

return key % arraySize;

}

public void insert(DataItem item){

int key = item.getkey();

int hashVal = hashFunc(key);

while(hashArray[hashVal] != null && hashArray[hashVal] != -1){ //-1指的是被删除过数据

hashVal ++;                                              项的数组单元

hashVal %= arraySize; //如果有必要则返回数组初始部位继续查询

}

hashArray[hashVal] = item;

}

当哈希表的数据项接近于填满哈希表时，会产生一种不好的现象“聚集”，这会使得哈希表处理数据的速度大大

下降，二次探测能有效避免聚集，假如线性探测的过程是x+1,x+2,x+3....那么二次探测的过程就是x+1,x+4,x+9.....

但是这样具有相同的哈希化后的值的数据又会产生“二次聚集”，因此我们又有了再哈希法，也就是将关键字用不同的

哈希函数再哈希化一边将结果作为探测的“步长”。现在已知一个哈希函数能很好满足这个想法：stepSize = constant - (key % constant);

其中constant是小于数组容量的一个质数。下面我简单写下代码来体现这一方法如何插入数据：

public void insert(DataItem item){

int key = item.getKey();

int hashVal = hashFunc1(key);

int stepSize = hashFunc2(key);  //hashFunc2为再哈希化的哈希函数

while(hashArray[hashVal] != null && hashArray[hashVal] != -1){

hashVal += stepSize;

hashVal %= arraySize;

}

hashArray[hashVal] = item;

}

 

  “链地址法”的意思就是让数组里面存储的不是数据项而是链表下面用一个图来展示：

public void insert(Link theLink){

int key = theLink.getKey();

Link previous = null;

Link currunt = first;

while(currunt != null && key > current.getKey()){

previous = current;

current = current.next; 

}

if(previous == null)

first = theLink

else 

previous.next = theLink;

theLink.next = current;

}