[数据结构与算法]HashMap原理和实现

为什么要使用Map和Set容器？它们有何优点呢？

Map和Set容器专门是用来进行搜索的，搜索的效率与其实例化子类有关。
对于一般的数据搜索来说，都是静态类型的，在查找的过程中不会对数据进行插入和删除操作，我们有：
① 直接搜索：时间复杂度为O(N)，在元素较多的情况下效率较低；
② 二分查找：时间复杂度为O(${\log }_{2}N$)，要求搜索前数据有序；
那么在动态查找时，以上方法就不太适用了，我们引出Map和Set接口作为一种适合动态搜索的集合容器。

Map和Set常用方法

Map（Key-Value模型）

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

**Map.Entry<K,V>**是Map内部实现的用来存放<key, value>键值对映射关系的内部类。该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式。

//打印所有的键值对
HashMap<String, String> map = new HashMap<>();
for(Map.Entry<String,String> entry : map.entrySet()){
	System.out.println(entry.getKey()+"-->"+ entry.getValue());
}

总结：
① Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap；
② Map中存放键值对的Key是唯一的，value是可以重复的。且Key和Value都是可以为空的；
③ Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)；
④ Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)；
⑤ Map中键值对的Key不能直接修改，value可以修改（setValue()方法），如果要修改key，只能先将该key删除掉，然后再来进行重新插入。

面试题 : HashMap和TreeMap的区别
相同点：两者都实现了Map接口，并且都是线程不安全的。
不同点：
HashMap基于哈希表（哈希桶）实现。使用HashMap要求添加的类明确定义了hashCode()和equals()方法，我们也可以重写hashCode()和equals()方法，为了优化HashMap空间的使用，可以调优初始容量和负载因子。
增删查改的时间复杂度为O(1)，通过哈希函数直接计算关键字的哈希地址，可以获取键值，具有很快的访问速度。但是HashMap插入顺序和打印顺序不一致。
TreeMap基于红黑树实现，TreeMap没有调优选项，因为该树总处于平衡状态。
增删查改时间复杂度为O(${\log }_{2}N$)，TreeMap实现了SortedMap接口，能够把它保存的记录根据Key排序，默认是按Key值的升序排序，也可以指定排序的比较器，得到的输出是有序的。Key必须要能进行比较，否则会出现ClassCastException异常。

Set （纯Key模型）

Set继承自Collection接口，是一个不允许出现重复元素且无序的集合，主要有HashSet和TreeSet两大实现类。
在判断重复元素时，Set集合会调用hashCode()和equal()方法来实现；
HashSet是哈希表结构，主要利用HashMap的key来存储元素，计算插入元素的hashCode来获取元素在集合中的位置；
TreeSet是红黑树结构，每一个元素都是树中的一个节点，插入的元素都会进行排序；

总结：
① Set的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的；
② 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序；
③ Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入；
④ Set中可以插入null的Key。
有关哈希表的题目

哈希表

对于顺序结构和平衡树结构来说，搜索的效率取决于搜索过程中元素的比较次数，顺序查找时间复杂度为O(N)，平衡树时间复杂度为树的高度O(${\log }_{2}N$)，我们理想的搜索方法是可以不经过任何的比较，一次性能找到要搜索的元素。通过建立该元素的存储位置和它的关键码之间的一对一映射关系，提高搜索的效率。因此，哈希表出现了。
哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)。
eg.

哈希冲突

不同关键字通过哈希函数计算出相同的哈希地址，这种现象称为哈希冲突（或哈希碰撞）。
我们需要清楚的是，哈希冲突是必然的，我们能做的只是尽量去降低冲突发生的概率。有两个角度：

1. 设计哈希函数
   常见的哈希函数：
   ① 直接定制法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况；
   ② 除留余数法：地址数为m，取一个不大于m，但最接近或者等于m的质数 p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址；
   ③ 平方取中法：假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况；
   ④ 折叠法：将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况；
   ⑤ 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法；
   ⑥ 数学分析法：通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。
2. 调节负载因子
   负载因子：填入表中的元素个数 / 散列表的长度
   负载因子和冲突率成正比，已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

解决冲突

既然冲突不可避免，那么我们就去尽量解决它。一般的解决方法有两个。

闭散列（开放定址法）

当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的 下一个空位置中去哪儿如何寻找下一个空位置呢？
① 线性探测：通过哈希函数获取待插入元素在哈希表中的位置，如果该位置被占用，从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
缺点：产生冲突的数据会挤在一块儿
② 二次探测：找下一个空位置的方法为：$H_i$ = ( $H_0$+$i^2$ )% m, 或者：$H_i$ = ( $H_0$-$i^2$ )% m。其中：i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

开散列（链地址法/开链法）

这是我们的重点！！！因为Java JDK1.8中解决冲突使用开散列，并且采用尾插法。
首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

从上图例子可以看出，开散列中的每个桶中放的都是哈希冲突的元素。
在JDK1.8中，当桶中的元素个数（单链表长度）>=8，并且数组的长度>=64时，单链表就会变为红黑树，搜索效率显著提高。源码中默认的capacity数组长度为64，装填因子为0.75。
附JDK1.8 HashMap源码解析参考：HashMap源码解析 感谢大佬的分享！
?重点掌握put()和get()方法的执行流程以及初始设置！

面试题：在HashMap中，hashCode()和equals()区别是什么？
hashCode()用于定位当前元素需在当前数组（桶）的下标
equals()用于在hashCode()定位的某个下标中，遍历链表比较两个key是否相同（键值唯一的依据）
hashCode()相同,equals()不一定相同；equals()相同，hashCode()一定相同。

面试题：哈希表的时间复杂度为什么是O(1)？
在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是O(1) 。

代码实现哈希桶

自己实现一个简易的哈希桶（put()/get()/负载因子/扩容）
如果HashMap中需存放自己自定义的数据类型，那么这个类型一定要同时重写hashCode()和equals()方法！

public class HashBucket {
    //定义Node结点
    public static class Node{
        public int key;
        public int value;
        Node next;
        //带两个参数的构造方法
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public Node[] array = new Node[10];
    public int usedSize = 0;

    //put插入
    public void put(int key, int value){
        //计算要插入的下标
        int index = key % array.length;
        //在链表中查找key所在的结点，如果有的话，替换value
        Node cur = array[index];
        while(cur!=null){
            if(key == cur.key){
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node node = new Node(key,value);
        //采用头插法
        node.next = array[index];
        array[index] = node;
        usedSize++;

        //判断是否需要扩容
        if (loadFactor()>=0.75){
            resize();
        }
    }

    private int get(int key){
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur!=null){
                if(cur.key == key){
                    return cur.value;
                }
                cur = cur.next;
            }
        }
        return -1;  //没找到
    }

    private void resize() {
        //2倍扩容
        Node[] newArray = new Node[array.length*2];
        for(int i=0;i<array.length;i++){
            Node cur = array[i];
            Node curNext = null;
            while (cur!=null){
                curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }

    private double loadFactor() {
        return usedSize*1.0/array.length;
    }

    public static void main(String[] args) {
        HashBucket hashBucket = new HashBucket();
        hashBucket.put(4,1);
        hashBucket.put(9,2);
        hashBucket.put(14,3);
        hashBucket.put(19,4);
        System.out.println(hashBucket.get(19));
    }
}

注意：
① HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set；
② java 中使用的是哈希桶方式解决冲突的；
③ java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）；
④ java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。

?常见面试题：
1.如果new HashMap(19)，哈希桶数组此时应该为多少？
官方要求我们要输入一个2的N次幂的值，找一个超过19并且离19最近的2的N次幂的值，32！即为初始数组容量。
2.HashMap什么时候开辟bucket数组占用内存呢？
第一次调用put()时
3.HashMap何时扩容？
根据负载因子大小，默认是0.75，超出loadFactor*initialCapacity后就会resize
4.当两个对象的hashCode相同会发生什么？
哈希冲突！
5.如果两个键的hashCode相同，如何获取值对象？
在当前hashCode的数组位置开始遍历链表。
6.重新调整hashMap大小存在什么问题？
rehash！