06-散列(Hash)基础分析

散列(Hash)基础分析

什么是散列表？

散列表又称哈希表(Hash Table)，是一种将键(key)映射到值的数据结构，是对数组应用的推广,它基于“散列设计算法”将关键码（Key）映射为数组下标，然后将关键码对应的数据存储在数组中。这个过程类似于字典设计(基于字典关键码找到对应的词条)。如图所示：

其中，图中的buckets为桶数组(又称“散列表”-hash table)，桶数组中基于桶(bucket)直接存储数据。

如何理解散列设计？

散列设计是一种设计思想，它通过一定的算法将key转换为散列表的下标。这种对算法的封装我们称之为“散列函数”，通过散列函数计算得出的值称之为“散列值”(或哈希值)。如下图所示：

其中，图中的0,1,2,3为通过散列函数计算得出的哈希值，这些值对应哈希表中的数组下标。我们在设计散列算法时，通常要遵循几个基本原则,例如：

1. 散列(Hash)计算得到的散列值应该是一个非负整数；（因为数组的下标从0开始）
2. 如果 key1 = key2，那 hash(key1) == hash(key2)；（相同key，得到的散列值也相同）
3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)；（不好确定）

在进行散列设计时，对于key不同的计算，应尽量保证hash值也不相同，但这样的设计，可能要付出的更多的计算成本，时间成本。所以key不同，hash值相同的这种现象还是会存在的，我们把它称之为散列冲突。如下图所示：

如何解决散列冲突？

散列设计既然无法避免散列冲突，那出现了散列冲突以后，如何应对呢？我们常用的解决方案有两类，开放寻址法（open addressing）和链表法（chaining）。

开放寻址法解决散列冲突：

当出现了散列冲突以后，开放寻址是要重新探测一个新的空闲位置，然后将其插入。那如何重新探测新的位置呢？常用的方法有线性探测(Linear Probing)，二次探测（Quadratic probing）和双重散列（Double hashing）等，我们首先来看一下线性探测(Linear Probing)，如下图所示：

在线性探测中，每次探测的步长是 1，那它探测的下标序列依次是 hash(key)+0，hash(key)+1，hash(key)+2……。你可能会发现，此方法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下， 我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。对于二次探测，跟线性探测很像，它每次探测的步长就变成了原来的“2次方”，其探测的下标序列就是 hash(key)+0，hash(key)+1^2 ，hash(key)+2^2 ……。 所谓双重散列，意思就是不仅要使用一个散列函数。可能要使用一组散列函数 hash1(key)，hash2(key)，hash3(key)…。总之，开放寻址中，不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。

链表法解决散列冲突：

当出现了散列冲突以后，链表法相比开放寻址法，它要简单很多。也是一种更加常用的散列冲突解决办法。 在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一张链表，所有散列值相同的元素，我们都放到相同槽位对应的链表中。如图所示：

我们在散列表中进行数据插入的时，通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当删除一个元素时，我们同样通过散列函数计算出对应的槽位， 然后遍历链表找到对应元素进行删除即可。其时间复杂度可能会大一些，例如O(K)。

Java中散列应用分析与实践？

基于散列设计思想,实现简易的HashMap,用于存储多个键值对，代码如下：

package com.cy.pj.ds.hash;

import java.util.ArrayList;

/**简易散列表操作实现*/
public class SimpleHashMap {
    //定义链表中节点类型
    class HashNode{
        private Object key;
        private Object value;
        private HashNode next;
        public HashNode(Object key,Object value) {
            this.key=key;
            this.value=value;
        }
    }
    //定义散列表(桶数组)
    private ArrayList<HashNode> bucketArray;
    //定义桶的个数
    private int numBuckets;
    //定义size记录有效元素个数
    private int size;
    //通过构造方法对散列表进行初始化
    public SimpleHashMap(int numBuckets) {
        this.numBuckets=numBuckets;
        bucketArray=new ArrayList<>();
        for(int i=0;i<numBuckets;i++) {
            bucketArray.add(null);
        }
    }
    //定义一个散列函数
    public int hash(Object key) {
        int hashCode=key.hashCode();
        return hashCode%numBuckets;
    }
    //定义数据添加函数
    public void put(Object key,Object value) {
        //1.基于key获取其散列值(下标值)
        int index=hash(key);
        //2.获取散列表中的桶对象(链表节点)
        HashNode head=bucketArray.get(index);
        //3.检测链表中是否有key相同的元素，key相同值覆盖
        while(head!=null) {
            if(head.key.equals(key)) {
                head.value=value;
                return;
            }
            head=head.next;
        }
        //4.添加新的key/value到桶中
        //4.1获取指定下标对应的桶对象的head节点
        head=bucketArray.get(index);
        //4.2创建新的node节点
        HashNode newNode=new HashNode(key, value);
        //4.3将新节点设置为当前桶中的头节点
        newNode.next=head;
        //4.4将指定index位置的元素设置为新的链表头节点
        bucketArray.set(index, newNode);
        //4.5执行size++操作
        size++;
        //5.对散列表进行扩容设计
        if((1.0*size)/numBuckets>=0.8) {
            ArrayList<HashNode> temp=bucketArray;
            numBuckets*=2;//将桶个数设置为原有桶个数的2倍
            bucketArray=new ArrayList<>();//新的散列表
            for(int i=0;i<numBuckets;i++) {
                bucketArray.add(null);
            }
            size=0;
            //将原有散列表中的数据拷贝到新的散列表中
            for(HashNode headNode:temp) {
                while(headNode!=null) {
                    put(headNode.key, headNode.value);
                    headNode=headNode.next;
                }
            }
        }
    }
    public Object get(Object key) {
        //1.对key进行散列求值
        int index=hash(key);
        //2.获取index对应的桶
        HashNode head=bucketArray.get(index);
        //3.获取key对应的value值
        while(head!=null) {
            if(head.key.equals(key)) {
                return head.value;
            }
            head=head.next;
        }
        return null;
    }
    //基于key删除指定元素
    public Object remove(Object key) {
        //1.对key进行散列求值
        int index=hash(key);
        //2.获取index对应的桶
        HashNode head=bucketArray.get(index);
        //3.在桶查找key对应的节点，然后进行删除操作
        HashNode prev=null;
        while(head!=null) {
            if(head.key.equals(key))break;
            prev=head;
            head=head.next;
        }
        if(head==null)return null;
        if(prev!=null) {
            prev.next=head.next;
        }else {
            bucketArray.set(index, head.next);
        }
        size--;
        return head.value;
    }

    public int size() {
        return size;
    }
    public static void main(String[] args) {
        SimpleHashMap map=new SimpleHashMap(2);
        map.put("this", 1);
        map.put("coder", 2);
        map.put("this", 3);
        map.put("hello", 4);
        map.put("welcome", 5);
        System.out.println(map.size);
        System.out.println(map.get("coder"));
        map.remove("this");
        System.out.println(map.size);
        System.out.println(map.get("this"));
    }
}
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

如何对散列(Hash)函数进行设计？

对于散列函数的设计，一般要遵循如下几个原则：

▪ 对于给定的key，经过散列计算，得到的散列值应该是一个非负整数。
▪ 对于相同的key，经过同样的散列计算，应该得到的散列值也相同。
▪ 对于不同的key，经过相同的散列计算，得到的散列值应尽量不相同。

除此之外,还要尽量少散列冲突，即使有冲突，也要保证将数据能够均匀的分配到散列表的每个桶内。

数据插入时线性探测过程是怎样的？

当我们向散列表中插入数据时，如果某个数据经过散列计算之后，要进行存储的位置已经被占用了，也就是说出现了散列冲突。此时就需要从当前位置开始，依次向后查找，检查是否有空闲位置，直到找到插入位置为止。

开放寻址有什么优势和劣势？

开放寻址是在散列冲突以后，基于某种策略重新探测新的空闲位置的方法。
▪ 优势：查询速度快(数据都在数组中),序列化也方便。
▪ 劣势：数据量越大冲突的几率就越大，探测时间就会越长。
总之，当数据量比较小、装载因子小的时候，适合采用开放寻址法。

散列冲突中链表的解决方案的时间复杂度是多少？

当插入数据的时候，我们需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以插入的时间复杂度为O(1)。当查找、删除一个元素时，首先需要通过散列函数计算对应的槽位，然后依次遍历链表中的元素。对于散列比较均匀的散列函数，每个桶内的链表的节点个数k=n/ m，其中n表示散列表中数据的个数，m表示散列表中槽的个数，所以是时间复杂度为O(k)。

链表方式解决散列冲突有什么优点？

链表方法是在散列冲突以后，将元素作为链表头节点或尾节点插入到散列值对应的散列表位置。
▪ 优势，内存利用率高，解决冲突的时间更快。
▪ 缺陷，桶中节点元素内存地址不连续，导致查询性能可能会降低。
总之，基于链表的散列冲突处理方法比较适合存储大对象（此时可忽略指针占用空间）、大数据量的散列表。而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

Java中HashMap源码分析？

1）初始大小设计

HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容(2的n次方)的次数，这样会大大提高 HashMap 的性能。

2）装载因子和动态扩容设计

最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity表示散列表的容 量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

3）为什么扩容因子为0.75?
为什么不是0.5,也不是1呢?是因为这个0.75是在时间和空间上取的相对平衡值,假如在1的时候扩容,数组中数据越多,产生散列冲突的几率越大,一旦产生散列冲突数据就会转换为链表进行存储,而链表方式会影响查询效率. 假如在0.5时进行扩容,但又没有那么多元素要进行存储,可能会产生大量的空间浪费.

4)散列冲突及解决方案设计

HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现 链表过长的情况，一旦出现链表过长，则会严重影响 HashMap 的性能。 于是，在 JDK1.8 版本中，为了对 HashMap 做进一步优化，官方引入了红黑树。而当链表长度太 长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数小于或等于6的时候，又会将红黑树转化为链表。因为在数据量 较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

5）为什么是链表长度达到8的时,进行红黑树转换?

经过大量计算、测试，链表的长度达到8的几率已经很小,所以可以直接基于8作为链表转红黑树的边界值。
为什么不是大于呢，因为链表长度较长查询效率就会越低。为什么不是7呢？链表结点数量比较小时，应用
红黑树还要进行树的平衡设计，需要的成本相对比较高。

6. 为什么红黑树节点个数小于6的时要转换链表呢?

假如是7则数据在链表和红黑树之间来回转换可能会比较频繁，这样就需要更长的时间消耗。

7)线程(thread)安全设计

HashMap本身并不是线程安全的对象，所以仅可以应用在线程安全的环境。在线程不安全的环境推荐使用ConcurrentHashMap，此map在JDK8中采用了CAS算法保证对map的操作是线程安全的；

JDK7和JDK8中的hashmap有什么不同？

1.7中采用数组+链表，1.8采用的是数组+链表/红黑树，即在1.8中链表长度超过一定长度后就改成红黑树存储。

1.7 的底层节点为Entry，1.8 为node ，但是本质一样，都是Map.Entry 的实现
1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。

1.7是采用表头插入法插入链表，1.8采用的是尾部插入法。

在1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在1.8中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

Hashmap中的负载因子为什么是0.75？

负载因子为0.75f 是空间与时间的均衡

如果负载因子小，意味着阈值变小。比如容量为10 的HashMap，负载因子为0.5f，那么存储5个就会扩容到20，出现哈希冲突的可能性变小，但是空间利用率不高。适用于有足够内存并要求查询效率的场景。

相反如果阈值为1 ，那么容量为10，就必须存储10个元素才进行扩容，出现冲突的概率变大，极端情况下可能会从O(1)退化到O(n)。适用于内存敏感但不要求要求查询效率的场景

为何HashMap的数组长度一定是2的次幂？

数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀，减少hash冲突。保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)。。、、

说说ConcurrentHashMap对象？

ConcurrentHashmap(1.8)这个并发集合是线程安全的HashMap，在jdk1.7中是采用Segment + HashEntry + ReentrantLock的方式进行实现的，而1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现。

JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）
JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档。

总结(summary)