Java--HashMap原理--数据结构/扩容机制/存取机制/hashCode方法

原文网址：Java--HashMap原理--数据结构/扩容机制/存取机制/hashCode方法_IT利刃出鞘的博客-CSDN博客

概述

本文介绍Java中HashMap的原理，包括：数据结构、扩容机制、存取机制、hashCode方法。

数据结构

数组和链表

数据结构中有数组和链表来实现对数据的存储，但这两者各有利弊。

项	数组	链表
内存占用	占内存大。（存储区间连续）	占内存大。（存储区间不连续）
查找的速度	快。（时间复杂度小，为O(1)）	慢。（时间复杂度很大，为O(N)）
插入和删除的速度	慢。	快。

哈希表

哈希表：综合数组和链表的特性：查找（寻址）容易，插入删除容易、占空间中等的数据结构。

哈希表有多种不同的实现方法，HashMap则使用的是拉链法，也叫作【链地址法】。

哈希表的数组的初始长度为16，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中:

12%16=12,28%16=12,108%16=12,140%16=12

所以12、28、108以及140都存储在数组下标为12的位置。

存取机制

键值对的数据

每个键值对都是一个Node对象，它实现了Map.Entry接口。Node有四个属性：hash、key、value、next（下一个节点）。

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
    }
    // 其他代码
}

既然是线性数组，为什么能随机存取？这里HashMap用了一个小算法，大致是这样实现：

// 存储时:
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;
 
// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

put

哈希冲突

若两个key通过hash%Entry[].length得到的index相同，怎么处理？HashMap用到的链表。Entry类里面有一个next属性，指向下一个Entry。

打个比方：
第一个键值对A进来，通过计算其key的hash得到的index=0，记做：Entry[0] = A。
一会后又进来一个键值对B，通过计算其index也等于0，HashMap会这样做:B.next = A,Entry[0] = B；
如果又进来C，index也等于0，那么C.next = B,Entry[0] = C；
这样我们发现index=0的地方其实是利用单链表的头插法存取了A,B,C三个键值对，他们通过next这个属性链接在一起。所以会发生覆盖的情况，数组中存储的总是最后插入的元素。到这里为止，HashMap的大致实现，我们应该已经清楚了。

transient Node[] table;
transient int size;
static final int TREEIFY_THRESHOLD = 8;
int threshold;

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 若链表的节点数大于等于8，则转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果key在链表中已存在，则替换为新value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    //先定位到数组元素，再遍历该元素处的链表
    for (Entry e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

null key的存取

null key总是存放在Entry[]数组的第一个元素。

private V putForNullKey(V value) {
    for (Entry e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

private V getForNullKey() {
    for (Entry e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

确定数组

index：hashcode % table.length取模

HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标；算法如下：

// Returns index for hash code h.
static int indexFor(int h, int length) {
    return h & (length-1);
}

按位取并，作用上相当于取模mod或者取余%;这意味着数组下标相同，并不表示hashCode相同。

table初始大小

public HashMap(int initialCapacity, float loadFactor) {
    .....
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

注意table初始大小并不是构造函数中的initialCapacity！！

而是 >= initialCapacity的2的n次幂！

哈希冲突

其他网址

哈希冲突及四种解决方法_好奇心大爆炸-CSDN博客_哈希冲突
关于hash冲突的初步理解_小哲的无何有镜-CSDN博客_hash冲突
数据结构与算法：hash冲突解决 - 知乎

简介

解决哈希冲突有以下四种方法

链地址法
开放定址法
再哈希法
建立公共溢出区

1.链地址法

对于相同的哈希值，使用链表进行连接。（HashMap使用此法）

优点

处理冲突简单，无堆积现象。即非同义词决不会发生冲突，因此平均查找长度较短；
适合总数经常变化的情况。（因为拉链法中各链表上的结点空间是动态申请的）
占空间小。装填因子可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计
删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点

查询时效率较低。（存储是动态的，查询时跳转需要更多的时间）
在key-value可以预知，以及没有后续增改操作时候，开放定址法性能优于链地址法。
不容易序列化

2. 开放定址法

当关键字key的哈希地址p =H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，若p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

即：Hi=（H（key）+di）% m （i=1，2，…，n）

开放定址法有下边三种方式：

线性探测再散列
1. 顺序查看下一个单元，直到找出一个空单元或查遍全表
2. di=1，2，3，…，m-1
二次(平方)探测再散列
1. 在表的左右进行跳跃式探测，直到找出一个空单元或查遍全表
2. di=1^2，-1^2，2^2，-2^2，…，k^2，-k^2 ( k<=m/2 )
伪随机探测再散列
1. 建立一个伪随机数发生器，并给一个随机数作为起点
2. di=伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
  
  例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。
  
  如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。
  
  如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。
  
  如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

优点

容易序列化
若可预知数据总数，可以创建完美哈希数列

缺点

占空间很大。（开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间）
删除节点很麻烦。不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

3.再哈希法

提供多个哈希函数，如果第一个哈希函数计算出来的key的哈希值冲突了，则使用第二个哈希函数计算key的哈希值。

优点

不易产生聚集

缺点

增加了计算时间

4.建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

扩容机制

其他网址

HashMap的扩容机制---resize()_数据结构与算法_潘建南的博客-CSDN博客
HashMap之扩容机制 - 简书
HashMap的扩容机制------resize()_java_IM_MESSI的博客-CSDN博客
hashMap扩容机制_java_mengyue000的博客-CSDN博客

何时扩容

HashMap是懒加载，构造完HashMap对象后，若没用 put 来插入元素，HashMap不会去初始化或者扩容table。

首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化。
非首次调用put方法时，若HashMap发现size（数组大小）大于threshold（阈值）（当前数组的大小乘以加载因子的值），则会调用resize方法进行扩容。

数组是无法自动扩容的，所以只能是换一个更大的数组去装填以前的元素和将要添加的新元素。

resize()概述

判断扩容前的旧数组容量是否已经达到最大（2^30）了
1. 若达到则修改阈值为Integer的最大值（2^31 - 1），以后就不会扩容了。
2. 若没达到，则修改数组大小为原来的2倍
以新数组大小创建新的数组（Node[]）
将数据转移到新的数组（Node
[]）里
1. 不一定所有的节点都要换位置。
  1. 比如：原数组大小为16，扩容后为32。若原来有hash值为1和17两个数据，他们对16取余都是1，在同一个桶里；扩容后，1对32取余仍然是1，而17对32取余却成了17，需要换个位置。
    1. 对应的代码为：if ((e.hash & oldCap) == 0) 若为true，则不需要换位置。
返回新的Node[] 数组

类	初始容量	最大容量	扩容时倍数	加载因子	底层实现
HashMap	2^4	2^30	n * 2	0.75	Map.Entry
HashSet	2^4	2^30	n * 2	0.75	HashMap
HashTable	11	Integer.MAX_VALUE - 8	n*2 + 1	0.75	Hashtable.Entry

HashMap中，哈希桶数组table的长度length大小必须为2的n次方(非质数)，这是一种非常规的设计，常规的设计是把桶的大小设计为质数。相对来说质数导致冲突的概率要小于非质数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为质数的应用（Hashtable扩容后不能保证还是质数）。

HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

源码

HashMap#resize()

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Node[] table;
int threshold;
final float loadFactor;

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) // 红黑树
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) { // 重点1：判断节点在resize之后是否需要改变在数组中的位置
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 重点2：将某节点中的链表分割重组为两个链表：一个需要改变位置，另一个不需要改变位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

hashCode方法

其他网址

Java String的hashcode()方法实现_timothytt的博客-CSDN博客

源码(String#hashCode)

String#hashCode

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

为什么乘31呢？

选31是因为它是一个奇素（质）数，这里有两层意思：奇数 && 素数。

1.为什么是奇数，偶数不行？

因为如果乘子是个偶数，并且当乘法溢出的时候（数太大，int装不下），相当于在做移位运算，有信息就损失了。

比如说只给2bit空间，二进制的10，乘以2相当于左移1位，10(bin)<<1=00，1就损失了。

2.为什么是素数？

作者说：你问我我问谁，这是传统吧。素数比较流弊。

那么，问题又来了，那么多个奇素数，为什么就看上了31呢。

3.为什么偏偏是31？

h*31 == (h<<5)-h; 现代虚拟机会自动做这样的优化，算得快。

再反观这种“选美标准”下的其它数，

h*7 == (h<<3)-h; // 太小了，容易hash冲突

h*15 == (h<<4)-h; // 15不是素数

h*31 == (h<<5)-h; // 31既是素数又不大不小刚刚好

h*63 == (h<<6)-h; // 63不是素数

h*127 == (h<<7)-h; // 太大了，乘不到几下就溢出了

实例追踪

"abc".hashCode()

hash为：0
value为：[a, b, c]

第一次循环：h = 0 + 97 = 97

第二次循环：h = 31 * 97 + 98 = 3105

第三次循环：h = 3105 * 31 + 99 = 96354

其他网址

HashMap设计原理、HashMap的数据结构、HashMap源码实现_此处省略三千字-CSDN博客
6 数据结构 - 6.5 HashMap - 《Simon 的技术笔记》 - 书栈网 · BookStack

Java--HashMap原理--数据结构/扩容机制/存取机制/hashCode方法

Java相关栏目本月热门文章