哈希表的原理

冷不防 2024-03-17 19:28 91阅读 0赞

## 哈希概念 ##

线性表、树结构的查找方式都是以关键字的比较为基础，查找效率比较低，**顺序表的时间复杂度是O（n），平衡树中为树的高度，即O（logn）**，搜素的效率取决于搜索过程的元素比较次数。

**理想的搜素方法**：可以用**不经过比较，一次直接从表中得到要搜素的元素**。如果构造一种存储结构，通过某种函数（**hashFunc**）使元素的存储位置与他的关键字之间能够建立**一一映射**的关系，那么在查找元素的时候,就可以很快寻找到该元素，这就是**哈希**的思想.

## 哈希函数 ##

**插入元素**

根据待插入的元素的关键字码，以此函数计算出该元素的存储位置并且按照此位置进行存放

**搜素元素**

对元素的关键字码进行同样的计算，把求得函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键字码相同，则搜素成功。

此方法即为哈希（散列）方法，哈希（散列）方法中使用的转换函数称之为哈希（散列）函数，构造出来的结构就是哈希表（hashTable）（或者散列表）。

例如：数据集合\{1，7，6，4，5，9\}；

哈希函数设置为：hash（key）= key%capacity;(capacity代表的是底层空间总大小可以理解成元素个数)

![0b78a6041b6f45f7a0b3493f6d15064a.png][]

用该方法进行搜素的时候不必多次进行比较可以直接找到想找的关键字，但是我们就会出现一个问题：如果再次插入一个44怎么办呢？这就会引出下面的部分，哈希冲突。

## 哈希冲突： ##

**概念：**

对于两个关键字ki,kj（i != j）有ki != kj,但是有：Hash（ki）== Hash（kj）即：**不同的关键字通过哈希函数计算出相同的哈希地址，这种现象称之为哈希冲突。**

**冲突的避免**

首先我们要明确疑点，由于我们哈希表底层数组容量往往小于实际要存储的数量，这就导致了一个问题，**冲突是必然的，**但是我们可以**降低冲突率。**

**哈希函数的设计**

**1、直接定制法**

取关键字的某个线性函数为散列地址：Hash（key）=A\*key+B （即是一个y=ax+b的函数，如计数排序数字91存储在（91-90）的下标上）**优点：简单、均匀 缺点**：**需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况。**

**2、除留余数法**

这个就是我们上面所介绍的方法，标准的官方说法是设散列表中允许的地址数为m（如果10个数据m的范围就是0-9），取一个不大于m的数，但是最接近或者等于m的质数p作为除数，按照哈希函数Hash（key）= key%p（p<=m），将关键字码转换为哈希地址。

还有很多的方法，但是使用的很少，所以这里不过多介绍。

**负载因子调节**

散列表的载荷因子定义为：![\\alpha][alpha]=填入表格的元素/散列表的长度

在java系统库中限制载荷因子为0.75如果大于这个数字就需要，降低载荷因子。

## 哈希冲突的解决 ##

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

**闭散列：也叫开放定址法，当哈希表没有被填满，说明哈希表还有空位置，那么可以把key存放到冲突位置的下一个空位置去。**那么如何寻找下一个空位置呢？

**1、线性探测**

比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标是4，所以理论上应该插入到4的位置，但是该位置已经存放了元素4，即发生了哈希冲突。

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

![6fb4b10197914e22b1e3b862b617bf9e.png][]

采用闭散列处理哈希冲突的时候，不能随便物理删除哈希表已经有的元素，若直接删除元素会影响其他元素的搜索。比如删除4，如果直接删除4，那么在查找44的时候就会受到影响。因此线性探测采用标记的伪元素来删除一个元素。

**2、二次探测**

线性探测的缺陷是产生冲突的元素堆积到一块，这与其找下一个元素位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免这样的问题，找下一个空位置的方法为：Hi=(H0+i²）%m或者Hi=(H0-i²）%m其中：i=1，2，3....H0是通过哈希函数计算出元素所在位置，m是表的大小。

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

**开散列/哈希桶（重点）**

**开散列：**开散列又叫链地址法（开链法），首先对关键码集合用哈希函数计算出哈希地址，具有相同的地址的关键码归于同一子集合，每一个子集称作一个桶，各个桶中的元素通过一个单链表连接器起来，各链表的头节点都存储在哈希表中。

![7f86539df53c48eb898bacba433e9059.png][]

**开散列，可以认为把一个大集合中的搜素问题转化到小集合中进行。**

代码实现：

public class Hashbucket {
        static class Node{
            private int key;
            private int value;
            private Node next;
    
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
        public Node[] array;
        public int useSize;
        private static final float DEFAULT_LOAD_FACTOR = 0.75f;
        public Hashbucket() {
            array=new Node[10];
        }
        public void put(int key,int value){
            Node node=new Node(key,value);
            int index= node.key%array.length;
            Node cur=array[index];
            //java1.8之后采用的是尾插法 这里采用头插法
            while(cur!=null){
                if(cur.key==key){
                    cur.value=value;
                    return;
                }
                cur=cur.next;
            }
            node.next=array[index];
            array[index]=node;
            useSize++;
            if(loadFactor()>DEFAULT_LOAD_FACTOR){
                resize();
            }
        }
        public void resize(){
            //二倍扩容
            Node[] tmpArray=new Node[array.length*2];
            for (Node node : array) {
                Node cur = node;
                while (cur != null) {
                    Node curNext = cur.next;
                    int index = cur.key % tmpArray.length;
                    //头插法
                    cur.next = tmpArray[index];
                    tmpArray[index] = cur;
                    cur = curNext;
                }
            }
            array=tmpArray;
        }
        public float loadFactor(){
            return array.length*1.0f/useSize;
        }
        public int get(int key){
            int index=key%array.length;
            Node cur=array[index];
            while(cur!=null){
                if(cur.key==key){
                    return cur.value;
                }
                cur=cur.next;
            }
            return -1;
        }
    }

这个代码中这个扩容部分我们要仔细的说一说，但负载因子大于0.75的时候，我们需要降低哈希冲突，因为我们的元素个数是一定的，所以我们就需要增大散列表的大小，但是当我们扩容的时候，我们会打乱原来的散列表，比如原来4和14都是在节点4的位置，当我们二倍扩容的时候我们就需要将14放到节点14的位置。

[0b78a6041b6f45f7a0b3493f6d15064a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7dd6cba24eab4dfdbd7a214c52cacd48.png
[alpha]: https://latex.csdn.net/eq?%5Calpha
[6fb4b10197914e22b1e3b862b617bf9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/ae03ed3382be4a07a6cd0ec701a2bb6a.png
[7f86539df53c48eb898bacba433e9059.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7c4b6828e0514caa8a328c56e61f59fc.png