哈希表(散列表)_哈希表的时间复杂度

哈希表

1.概念

哈希表,也叫散列表,增删改查的时间复杂度均为O(1)

在顺序结构以及平衡树种,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较.顺序查找时间复杂度为O(N),即便是平衡树,也要 O(logN)(树的高度).主要是取决于搜索过程中元素的比较次数

而哈希(散列)方法可以做到,不经过任何比较,一次直接从表中得到想要搜索的元素.其存储结构,是通过某种函数使元素的存储位置与它的关键码之间建立一一映射的关系,在查找时通过该函数就可以很快查找到该元素.

• 插入元素
  根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素
  对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功

该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)(或称散列表)

例如:数据集合{1,7,6,4,5,9}

我们将哈希函数设置为: hash(key) = key % capacity ,其中 capacity = 10

用该方法进行搜索,不必进行多次关键码的比较,因此搜索的速度比较快

我们只需要取对应下标即可.

但有个问题,如果按照上述哈希方式,向集合元素中插入元素44,会出现什么问题?

hash(44) = 44 % 10 = 4,但此时,4下标中已经有4了,也就是会产生冲突

2.关于冲突

像上面的 4 和 44的例子,按照相同的哈希函数计算出的哈希地址都为4.即不同关键字通过相同哈希函数计算出相同的哈希地址,这种现象就称为 哈希冲突 或 哈希碰撞 .

3.避免冲突

1)冲突是必然的

哈希表底层数组的容量往往是要小于实际要存储的关键字的数量的,也就是说冲突的发生是必然的,我们所能做的就是尽量的降低冲突率

2)避免冲突(法一): 设计合理的哈希函数

引起哈希冲突的以一个原因可能是: 哈希函数设计不够合理

设计原则:

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

常见的两种哈希函数:

• 直接定制法
  

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

• 除留余数法
  

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

注意: 哈希函数设计的越精妙,产生哈希冲突的可能性就越低,但是无法避免哈希冲突

3)避免冲突(法二): 调节负载因子

负载因子和冲突率的关系粗略演示:

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。
已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

上面关系图可以看出,负载因子越大,冲突率就越大.

4.解决冲突

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

1)解决冲突(法一): 闭散列

闭散列: 也叫开房地址法,当发生哈希冲突时,如果哈希表未被装满,说明哈希表中必然还有空位置,那么可以把 key 存放到冲突位置中的"下一个"空位置中去.

还是之前的例子,我们现在要将 44 插入到,这个哈希表中,44 理论山是要插入到 4 这个位置上的,但是那已经有了元素 4.也就是说此时发生了哈希冲突.我们可以通过下面那两种方式,寻找到下一个空位置

①线性探测:

• 通过哈希函数获取到待插入元素在哈希表中的位置
• 从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止.然后插入新元素

需要注意的是: 采用闭散列处理哈希冲突时候,不能随便删除哈希表中已有的元素.若直接删除元素,可能会影响到其他元素的搜索.比如删除元素4,后续查找 44 就会收到影响.

因此线性探测采用标记的伪删除法来删除一个元素

②二次探测

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

这样解决办法就变为 向前 或者 向后,从 1的次方,2的次方,3…这样子开始找,就避免了产生冲突的数据堆积在一块的情况,故称为二次探测

例如还是上面的例子,要插入 44,发现在4位置冲突了,然后进行查找空位,Hi = (4+1^2)%10 = 6;发现这也起冲突了,那么就继续查找, Hi = (4 + 2^2)%10 = 8.(H0 为 开始起冲突的位置.10则是哈希表长度,按照哈希函数进行计算得到)

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

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

2)解决冲突(法二): 开散列(哈希桶)

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

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

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

3)冲突严重的解决办法

哈希桶其实可以看做将大集合的搜索问题转化为小集合的搜索问题了,那如果冲突严重,就意味着小集合的搜索性能其实也是不佳的,这个时候我们就可以将这个所谓的小集合搜索问题继续转化:

• 每个桶的背后是一个哈希表
• 每个桶的背后是一颗搜索树

5.哈希桶(开散列)的实现

1)实现

//实现一个简单的哈希表(哈希桶)
public class HashBucket<K,V> {
    //定义一个链表节点
    static class Node<K,V>{
        private K key;
        private V value;
        private Node<K,V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;//最大负载因子

    private Node<K,V>[] elem;
    private int useSize;
    public HashBucket(){
//        this.elem = (Node<K,V>[]) new Object[10];
        this.elem = (Node<K,V>[]) new Node[5];//通过类型转换匿名对象
    }
    //哈希函数,进行计算要插入的位置
    public int hashFunction(K key,int arrLen){
        int kHash = key.hashCode();//求得哈希值
        //计算
        return kHash % arrLen;
    }
    public void put(K key,V value){
        if(isExceedLoad()){
            //超过最大负载因子,则进行扩容,且对数组(哈希表)进行调整(重新哈希)
            reSize();
        }
        //未超过最大负载因子,正常添加元素

        //计算要插入的位置
        int index = hashFunction(key,this.elem.length);
        Node<K,V> node = new Node<>(key,value);
        if(this.elem[index] == null){
            //如果为空,则直接插入
            this.elem[index] = node;
            this.useSize++;
        }else{
            //如果不为空
            //1.看是否有重复元素
            //2.进行尾插
            Node<K,V> cur = this.elem[index];
            while(cur != null){
                if(cur.key == node.key){
                    cur.value = node.value;//更新 value值
                    return;
                }
                //通过这个if,就能让最后cur挺在最后一个节点上
                if(cur.next == null){
                    break;
                }
                cur = cur.next;
            }
            cur.next = node;
            this.useSize++;
        }
    }

    private void reSize() {
        //对数组进行扩容,直接扩大2倍
        Node<K,V>[] newArr = Arrays.copyOf(this.elem,this.elem.length*2);
        //进行重新哈希
        for (int i = 0; i < this.elem.length; i++) {
            Node<K,V> cur = this.elem[i];
            //逐个取出元素
            while(cur != null){
                int index = hashFunction(cur.key,newArr.length);
                Node<K,V> node = new Node<>(cur.key,cur.value);
                if(newArr[index] == null){
                    newArr[index] = node;
                    this.useSize++;
                }else{
                    Node<K,V> pur = newArr[index];
                    while(pur != null){
                        if(pur.key == node.key){
                            pur.value = node.value;
                            break;
                        }
                        if(pur.next == null){
                            pur.next = node;
                            this.useSize++;
                            break;
                        }
                        pur = pur.next;
                    }
                }
                cur = cur.next;
            }
            this.elem[i] = null;//指空,回收得了
        }
        this.elem = newArr;
    }

    private boolean isExceedLoad() {
        //当前负载因子 = 元素个数 / 链表长度
        return this.useSize*1.0/elem.length > DEFAULT_LOAD_FACTOR;
    }

    public V get(K key){
        //找到要查询的位置所在的下标
        int index = hashFunction(key,this.elem.length);
        Node<K,V> cur = this.elem[index];
        while(cur != null){
            if(cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

2)性能分析

虽然哈希表一直在和冲突做斗争,但在实际使用过程中,我们认为哈希表的冲突率是不高的,冲突的个数是可控的,也就是每个桶的链表的长度是一个常数,所以,通常意义下,我们认为哈希表的插入/删除/查找时间复杂度是O(1)