哈希冲突解决的几种方式

哈希冲突解决的几种方式

哈希冲突是哈希表在使用时常见的问题，由于表空间的大小有限，不同关键字在通过相同哈希函数计算时很可能计算出相同的哈希地址。为了解决这个问题，我们可以从两个方面入手：一是通过合理设计哈希函数和调节负载因子来避免冲突；二是采用闭散列和开散列等方法来解决冲突。

哈希冲突

在哈希表的使用中，由于表空间的大小有限，不同关键字在通过相同哈希函数计算时很可能计算出相同的哈希地址，这种现象我们称为哈希冲突或哈希碰撞。哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

我们将降低冲突率的方式大概分为两大类，一类是通过前期合理的设计，尽可能的避免哈希冲突的发生，一类是在哈希冲突发生后想办法去存储原来的数值减少哈希冲突带来的危害。

哈希冲突-避免方式1-哈希函数的设计

为了避免哈希冲突，我们要让哈希函数尽可能的合理，哈希函数设计有以下原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，如果散列表有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

常见哈希函数：

1. 直接定制法--(常用)

• 取关键字的某个线性函数为散列地址：Hash（Key） = A*Key + B
• 优点：简单、均匀
• 缺点：需要事先知道关键字的分布情况
• 使用场景：适合查找比较小且连续的情况

2. 除留余数法--(常用)

• 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m)，将关键码转换成哈希地址

3. 平方取中法--(了解)

• 假设关键字为 1234 ，对它平方就是 1522756 ，抽取中间的 3 位 227 作为哈希地址；
• 再比如关键字为 4321 ，对它平方就是18671041 ，抽取中间的 3 位 671( 或 710) 作为哈希地址
• 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

tips：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

哈希冲突-避免方式2-负载因子调节

什么是负载因子？

负载因子是评估哈希冲突发生概率的一个指标，范围在0-1之间，越接近1，发生哈希冲突的概率越高,定义为α=填入表中的元素个数 / 散列表的长度。

对于开放定址法，在我们设计的哈希表中我们需要严格监控负载因子的大小，应该严格限制在0.7-0.8以下，比如Java的系统库限制了负载因子的大小严格为0.75，当负载因子过高时我们可以通过增大哈希表的数组大小来调整负载因子。

哈希冲突-解决方式1-闭散列

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个”空位置中去。那如何寻找下一个空位置呢？

1. 线性探测

现在需要插入元素 44 ，先通过哈希函数计算哈希地址，下标为 4 ，因此 44 理论上应该插在该位置，但是该位置已经放了值为4 的元素，即发生哈希冲突。

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

2. 二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi=(H0+i^2 )% m, 或者：Hi= (H0-i^2 )% m。其中： i = 1,2,3… ，H0是通过散列函数Hash(x) 对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过 0.5 ，如果超出必须考虑增容。

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

哈希冲突-解决方式2-开散列(哈希桶)

开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

这种方法也叫做哈希桶，哈希桶的Java代码实现如下：

// key-value 模型
public class HashBucket {
    private static class Node {
        private int key;
        private int value;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private Node[] array;
    private int size; // 当前的数据个数
    private static final double LOAD_FACTOR = 0.75;
    public int put(int key, int value) {
        int index = key % array.length;
        // 在链表中查找 key 所在的结点
        // 如果找到了，更新
        // 所有结点都不是 key，插入一个新的结点
        for (Node cur = array[index]; cur != null; cur = cur.next) {
            if (key == cur.key) {
                int oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }
        }
        Node node = new Node(key, value);
        node.next = array[index];
        array[index] = node;
        size++;
        if (loadFactor() >= LOAD_FACTOR) {
            resize();
        }
        return -1;
    }
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node next;
            for (Node cur = array[i]; cur != null; cur = next) {
                next = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
            }
        }
        array = newArray;
    }
    private double loadFactor() {
        return size * 1.0 / array.length;
    }
    public HashBucket() {
        array = new Node[8];
        size = 0;
    }
    public int get(int key) {
        int index = key % array.length;
        Node head = array[index];
        for (Node cur = head; cur != null; cur = cur.next) {
            if (key == cur.key) {
                return cur.value;
            }
        }
        return -1;
    }
}

我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数。

哈希表最大优势就是插入/删除/查找的时间复杂度都是O（1）。