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

太过爱你忘了你带给我的痛 2023-05-21 07:24 6阅读 0赞

### 文章目录 ###

*   *  解决哈希冲突两种常见的方法是：闭散列和开散列
     *  闭散列
     *  开散列/哈希桶
     *  代码实现哈希桶
     *  性能分析

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

## 闭散列 ##

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

**1. 线性探测**  
比如场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。  
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。  
插入**通过哈希函数获取待插入元素在哈希表中的位置**如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70]  
*采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。*

**2. 二次探测**  
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：H\_i = (H\_0 + i^2 )% m,  
或者：H\_i = (H\_0 - i^2 )% m。其中：i = 1,2,3…， H\_0是通过散列函数Hash(x)对元素的关键码 key进行计算得到的位置，m是表的大小。 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70 1]  
研究表明：当表的长度为质数且表装载因子a不超过0.5时，**新的表项一定能够插入，而且任何一个位置都不会被探查两次**。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。  
因此：**闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。**

## 开散列/哈希桶 ##

\*\*开散列法又叫链地址法(开链法)，**首先对关键码集合**用散列函数计算散列地址，\*\*具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70 2]  
**通过顺序表和链表实现（顺序表中存储的哈希函数的地址，除留余数法，顺序表的每个位置就是一个桶）**，开散列中每个桶中放的都是发生哈希冲突的元素。

**冲突严重时的解决办法**

1.  **每个桶的背后是另一个哈希表**
2.  **每个桶的背后是一棵搜索树**

## 代码实现哈希桶 ##

// 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) 。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70]: /images/20230521/75db401417834932bf4e45e7f0d73c9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70 1]: /images/20230521/0ca36e32900c4185b4db2a77f0004d50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x6aF85OTk5OQ_size_16_color_FFFFFF_t_70 2]: /images/20230521/e06be113bbe040daa129d14ea86dabed.png