Java集合实现（二） HashMap源码以及手写HashMap

Map是一种特殊的集合，没有继承Collection接口，Map存储的是键值对，提供key到value的映射。

一、解决哈希冲突的方法

解决哈希冲突的方法一般有：开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法。

• 开放定址法：从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
• 链接地址法（拉链法）：是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。（链表法适用于经常进行插入和删除的情况）
• 再哈希法：就是同时构造多个不同的哈希函数： Hi = RHi(key) i= 1,2,3 … k; 当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间
• 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区

二、HashMap底层实现

JDK1.7 实现        

        JDK1.7 中 HashMap 由 数组+链表 组成（“链表散列” 即数组和链表的结合体），数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（HashMap 采用 “链式地址法” 解决冲突），如果定位到的数组位置不含链表（当前 entry 的 next 指向 null ），那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为 ，因为最新的 Entry 会插入链表头部，即需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过 key 对象的 equals 方法逐一比对查找。

【原理图】：

​

JDK1.8 实现

        DK 1.7 中，如果哈希碰撞过多，拉链过长，极端情况下，所有值都落入了同一个桶内，这就退化成了一个链表。通过 key 值查找要遍历链表，效率较低。 JDK1.8 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

【原理图】：

​

 确定哈希桶数组索引位置（hash 函数的实现）

//方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
 int h;
 // h = key.hashCode() 为第一步 取hashCode值
 // h ^ (h >>> 16)  为第二步 高位参与运算
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二：
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有提取这个方法，而是放在了其他方法中，比如 put 的p = tab[i = (n - 1) & hash]
 return h & (length-1); //第三步 取模运算
}

【面试题引入】

HashMap 的长度为什么是 2 的幂次方？

为了能让 HashMap 存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀，Hash值的范围是 -2147483648 到 2147483647，前后加起来有 40 亿的映射空间，只要哈希函数映射的比较均匀松散，一般应用是很难出现碰撞的，但一个问题是 40 亿的数组内存是放不下的。所以这个散列值是不能直接拿来用的。用之前需要先对数组长度取模运算，得到余数才能用来存放位置也就是对应的数组小标。这个数组下标的计算方法是 (n-1)&hash，n 代表数组长度。

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了。

取余操作中如果除数是2的幂次则等价于其除数减一的与操作，也就是说 hash%length=hash&(length-1)，但前提是 length 是 2 的 n 次方，并且采用 & 运算比 % 运算效率高，这也就解释了 HashMap 的长度为什么是 2 的幂次方。

三、实现JDK1.7的简单HashMap

原理上文已经说明，HashMap底层就是数组+链表+红黑树，来吧，试试看自己实现简单的HashMap吧

1、Map接口

public interface Map {
 
    V put(K k, V v);
 
    V get(K k);
 
    int size();
 
    interface Entry {
        K getKey();
 
        V getValue();
    }
}

2、 HashMap实现

public class HashMap implements Map {
 
    private int size = 0;
 
    Entry[] table = null;
 
    public HashMap() {
        this.table = new Entry[16];
    }
 
    @Override
    public V put(K k, V v) {
        int index = hash(k);
        Entry entry = table[index];
        if (entry == null) {
            table[index] = new Entry<>(k, v, index, null);
        } else {
            table[index] = new Entry<>(k, v, index, entry);
        }
        size++;
        return table[index].getValue();
    }
 
    @Override
    public V get(K k) {
        int index = hash(k);
        Entry entry = table[index];
        if (entry == null) {
            //如果为空，返回空值
            return null;
        } else {
            //如果不为空，对比值匹配则返回
            while (entry != null) {
                if (hash(entry.getKey()) == index) {
                    return entry.getValue();
                }
                entry = entry.next;
            }
            return null;
        }
    }
 
 
    @Override
    public int size() {
        return size;
    }
 
    public int hash(K k) {
        int index = k.hashCode() % this.table.length;
        return index > 0 ? index : -index;
    }
 
    class Entry implements Map.Entry {
 
        K k;
        V v;
        int index;
        Entry next;
 
        public Entry(K k, V v, int index, Entry next) {
            this.k = k;
            this.v = v;
            this.index = index;
            this.next = next;
        }
 
        @Override
        public K getKey() {
            return k;
        }
 
        @Override
        public V getValue() {
            return v;
        }
    }
}

完结撒花…… 

深入了解Java集合-https://javakeeper.starfish.ink/interview/Collections-FAQ.html