CS►programing►lan►java►jdk►rt►util

【java源码系列】HashMap

历史

  • java 1.0 中没有HashMap，有HashTable
  • java 1.2 引入HashMap
  • java 7 基于哈希表的实现
  • java 8 采用的

hash

数据结构

1
2
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;

hash过程

流程

  1. 对key计算hashcode
  2. 将hashcode映射到有限bucket空间
  3. 在相应的bucket内，存储或查询相应的key

计算hashcode

java7

1
2
3
4
5
6
7
8
9
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k); // 麻蛋
    }
    h ^= k.hashCode();  // 按位异或
    h ^= (h >>> 20) ^ (h >>> 12);  // “扰动函数”。Java 8中这步已经简化了，只做一次16位右位移异或混合，而不是四次，但原理是不变的。
    return h ^ (h >>> 7) ^ (h >>> 4); // >>> 无符号右移运算符
}

基础知识:

  1. hashSeed 随机数的种子，详见..
  2. ^ 按位异或。作用:
  3. >>> 无符号右移运算符
    左移的规则：丢弃高位，0补低位
    右移的规则：丢弃低位，高位的空位补符号位，即正数补零，负数补1

右移的偏移量20，12，7，4是怎么来的呢？因为Java中对象的哈希值都是32位的，所以这几个数应该
就是把高位与低位做异或运算，

再看一下String类中hashcode的计算

1
2
3
4
5
6
7
8
9
10
11
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];  // 为什么取素数？为什么取31？
        }
        hash = h;
    }
    return h;
}

在存储数据计算hash地址的时候，我们希望尽量减少有同样的hash地址，所谓“冲突”。如果使用相同hash地址的数据过多，那么这些数据所组成的 hash链就更长，从而降低了查询效率！所以在选择系数的时候要选择尽量长的系数并且让乘法尽量不要溢出的系数，因为如果计算出来的hash地址越大，所 谓的“冲突”就越少，查找起来效率也会提高。

使用31的原因可能是为了更好的分配hash地址，并且31只占用5bits！

在java乘法中如果数字相乘过大会导致溢出的问题，从而导致数据的丢失.
而31则是素数（质数）而且不是很长的数字，最终它被选择为相乘的系数的原因不过与此！

分配hashcode到bucket

hashcode的取值空间太大，不能作为直接存储地址。因此要把hashcode分配到一定数量的bucket中，取值[0, capacity‐1]。

为了使每个key都能在冲突最小的情况下映射到[0,capacity)，通常有两种做法：

  1. capacity为素数，index = hashCode(key) mod capacity
  2. capacity为2的倍数，index = hashCode(key) & (capacity‐1)

java7中

1
2
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
index = hashCode(key) & (capacity‐1); // 映射到0,capacity-1之间(类似mod)

普通的哈希算法（也称硬哈希）采用简单取模的方式，将机器进行散列，这在cache环境不变的情况下能取得让人满意的结果，但是当cache环境动态变化时，这种静态取模的方式显然就不满足单调性的要求（当增加或减少一台机子时，几乎所有的存储内容都要被重新散列到别的缓冲区中）。

存储或查询 (get put)

java7的get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

java7的put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

rehash

java7的rehash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void resize(int newCapacity) {
    Entry[] newTable = new Entry[newCapacity]; // 创建新的entry array
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// Transfers all entries from current table to newTable.
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

复杂度？

一致性？

其他

1
2
3
4
 //  默认的平衡因子为0.75。过高的因子会降低存储空间但是查找的时间就会增加。
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
int MAXIMUM_CAPACITY = 1 << 30;   // 哈希表容量（也就是buckets或slots大小）
float DEFAULT_LOAD_FACTOR = 0.75f;

NUll keys always map to hash 0, thus index 0

横向对比

  • Hashtable
  • LinkedHashMap
  • TreeMap
  • EnumMap

VS Hashtable

HashMap 不是线程安全的

HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，主要区别在于 HashMap 允许 null key 和 null value，由于非线程安全，效率上可能高于 Hashtable。

VS

revisit

设计

参考

思考题

  • hashcode的计算？
  • Null key的处理？为什么
  • 常量
    • modCount的作用？
    • loadFactor的作用？
    • 为什么容量必须为2的指数倍（默认为16）？
    • 超容后，reshash的复杂度是多少？怎样降低复杂度？怎样保证一致性？
    • 容量超过Integer.MAX_VALUE怎么办？
    • hashSeed的影响？
  • 并发的影响？见
  • 如何做到key的排序？见
  • 为什么放到util呢？ Map类的操作对象是其他类，所以也属于工具类。当然也可以理解为普通类(封装类、组合类)

答案在文中寻找