哈希冲突解决(转载)

1. 哈希表(Hash table)

也称为哈希表。是字典的一种抽象。比如说你要查一个字，通过这个字的拼音首字母，找到这个字的页码，然后翻到那页找就行了。这种方法直接把查找时间复杂度降到了常数。但是要牺牲一定的计算索引的时间。计算索引的那个函数称为哈希函数 ( 散列函数)。

1.1. 常见的三种哈希结构：数组; set（集合）; map（映射）;

1.2. 原理

通过哈希函数把传入的key映射到符号表的索引上，可以使查找插入时间复杂度达到常数级别。

1.3. 哈希函数

相等的 key 产生相等的 哈希值
计算简单方便
哈希值 均匀分布。(若过度集中，则容易使效率降低到 o(n))

相等的 key 产生相等的哈希值

计算简单方便

哈希值均匀分布。(若过度集中，则容易使效率降低到 o(n))

2. Hash冲突

如果两个不同的 key 算出了同一个索引，此时就要用到一定的方法来解决哈希冲突。

哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是 拉链法 和 线性探测法。

用map确实可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

3. 拉链法

拉链法的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。这样的好处是，不怕冲突多；缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。拉链法要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

3.1. 实现步骤

得到一个 key
计算 key 的 hashValue
根据 hashValue 值定位到 data[hashValue] 。( data[hashValue] 是一条链表)
若 data[hashValue] 为空则直接插入
不然则添加到链表末尾

3.2. 代码实现

public class SeparateChainingHashST<Key,Value> {
        //这里的M需要根据实际情况调整
        public SeparateChainingHashST(int M) {
            this.M = M;
            st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
            for (int i=0;i<M;i++){
                st[i]=new SequentialSearchST<Key,Value>();
            }
        }

        private int hash(Key key){
            return (key.hashCode() & 0x7fffffff) % M;
        }
        public void put(Key k,Value v){
            int hashValue = hash(k);
            st[hashValue].put(k,v);
        }

        public Value get(Key k){
            int hashValue = hash(k);
            return st[hashValue].get(k);
        }
}

public class SeparateChainingHashST<Key,Value> {

//这里的M需要根据实际情况调整

public SeparateChainingHashST(int M) {

this.M = M;

st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];

for (int i=0;i<M;i++){

st[i]=new SequentialSearchST<Key,Value>();

}

private int hash(Key key){

return (key.hashCode() & 0x7fffffff) % M;

}

public void put(Key k,Value v){

int hashValue = hash(k);

st[hashValue].put(k,v);

}

public Value get(Key k){

int hashValue = hash(k);

return st[hashValue].get(k);

}

4. 线性探测法

线性探测直接使用数组来存储数据。可以想象成一个停车问题。若当前车位已经有车，则你就继续往前开，直到找到下一个为空的车位

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

4.1. 实现步骤

得到 key
计算得 hashValue
若不冲突，则直接填入数组
若冲突，则使 hashValue++ ，也就是往后找，直到找到第一个 data[hashValue] 为空的情况,则填入。若到了尾部可循环到前面。

4.2. 代码实现

public class LinearProbingHashST<Key,Value> {
    public LinearProbingHashST(int cap) {
        keys = (Key[]) new Object[cap];
        values = (Value[]) new Object[cap];
        M = cap;
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }
    public void put(Key key,Value value){
        //若当前数据含量超过了总容量的一半，则重新调整容量
        if(N>=M/2) resize(2*M);  
        int hashValue = hash(key);
        if (values[hashValue]==null){
            keys[hashValue] = key;
            values[hashValue] = value;
            N++;
        }
        else if(keys[hashValue].equals(key)){
            values[hashValue]=value;
        }
        else{
            while (values[hashValue] != null){
                hashValue = (hashValue+1)%M;
            }
            keys[hashValue] = key;
            values[hashValue] = value;
            N++;
        }
    }
    public Value get(Key key){
        int hashValue = hash(key);
        if (keys[hashValue]!=null&&!keys[hashValue].equals(key)){
            while (keys[hashValue]!=null &&keys[hashValue]!=key){
                hashValue = (hashValue+1)%M;
            }
        }
        return values[hashValue];
    }
}

public class LinearProbingHashST<Key,Value> {

public LinearProbingHashST(int cap) {

keys = (Key[]) new Object[cap];

values = (Value[]) new Object[cap];

M = cap;

}

private int hash(Key key){

return (key.hashCode() & 0x7fffffff) % M;

}

public void put(Key key,Value value){

//若当前数据含量超过了总容量的一半，则重新调整容量

if(N>=M/2) resize(2*M);

int hashValue = hash(key);

if (values[hashValue]==null){

keys[hashValue] = key;

values[hashValue] = value;

N++;

}

else if(keys[hashValue].equals(key)){

values[hashValue]=value;

}

else{

while (values[hashValue] != null){

hashValue = (hashValue+1)%M;

}

keys[hashValue] = key;

values[hashValue] = value;

N++;

}

public Value get(Key key){

int hashValue = hash(key);

if (keys[hashValue]!=null&&!keys[hashValue].equals(key)){

while (keys[hashValue]!=null &&keys[hashValue]!=key){

hashValue = (hashValue+1)%M;

}

return values[hashValue];

}

转载自用拉链法和线性探测法解决哈希冲突

赞赏

微信赞赏支付宝赞赏