HashMap

Posted on | Edited on | Comments: | Views:

HashMap在Java里是很常用的一种数据结构，今天来白话一下

定义

HashMap 在Java中用来存放Key-Value，作用类比Python的dictionary和Javascript的object。它的特点就是块，查询和插入的复杂度都是O（1），内存开销也是稳定的。

用法

1
2
3
Map map = new HashMap<String, Activity>(4);
map.put("a", AnimationActivity());
map.get("a");

哈希和散列

这俩个词是啥关系？emmmr，好比西红柿和番茄吧。一个是hash的音译一个是意译。所以听到什么哈希表和散列表不要奇怪，它们都在说同一个东西，哈希表叫法的最早来源可能是hashmap里的 Node<K,V>[] table.没错哈希表是一个数组，这是它curd操作复杂度O（1）的基石。

取模&取余

正数没有差别，区别在于负数向0取余，远离0取模

1
2
3
4
7 mod 4 = 3（商 = 1 或 2，1<2，取商=1）
-7 mod 4 = 1（商 = -1 或 -2，-2<-1，取商=-2）
7 mod -4 = -1（商 = -1或-2，-2<-1，取商=-2）
-7 mod -4 = -3（商 = 1或2，1<2，取商=1）

哈希值

Java所有类祖宗都是Object，Object里提供了hashCode（）的默认实现。hashCode又是通过identityHashCode获取，identityHashCode是一个native方法，根据对象在内存中的地址运算得到。我们可以通过重写hashCode来覆盖这个值，但System.identityHashCode()返回的值是不变的（内存没变的话）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
String a = "test"
String b = "test"

// 打印这两个值的hashcode发现是一样的，这是符合我们的实际使用场景的，可见String的hashCode是有重写过。
// 查看源码，可以看到String的hashCode是基于内容运算得到。
public int hashCode() {
        int h = hash;
        final int len = length();
        if (h == 0 && len > 0) {
            for (int i = 0; i < len; i++) {
                h = 31 * h + charAt(i);
            }
            hash = h;
        }
        return h;
    }

重写hashCode

为什么要重写hashCode？是因为我们希望对象的hashCode可以持久，对象不变hashCode也不变。但是Object基于内存得到的hashCode是会跟着内存地址由于各种原因变化的（比如GC）。如果我们需要重写hashCode，我们需要考虑三点：稳定性（hash值和对象属性相关）；要块；要离散，Effective java有以下建议：

域类型 计算
boolean c=(f?0:1)
byte,char,short,int c=(int)f
long c=(int)(f^(f>>>32))
float c=Float.floatToIntBits(f)
double long l = Double.doubleToLongBits(f) c=(int)(l^(l>>>32))
数组 对每个元素分别计算

Result = 31 * result + c

实现HashMap

有以上这些储备，我们自己也可以实现一个HashMap了

1
2
3
1，实例化一个数组Object [] table
2，写一个getTableIndex方法，用Object.hashCode() 对数组长度取模
3，拿到index就可以对table数组进行curd操作，时间复杂度也是O(1)

实现简单，但问题很明显，实际上这样实现的HashMap效率会非常低，原因是：

1
2
3
1，没考虑resize，而实际情况中HashMap需要经常动态resize，这样才能兼顾时间和空间的效率
2，即使不考虑空间复杂度，初始化一个很大的数组，不同的Object的hashCode还是有可能一样，这时就崩了
3，没支持范型，会很难用

所以JDK里的HashMap是采用数组加链表来实现（java 8后链表会和红黑树动态变换）。

HashMap的Hash

HashMap的重点在Hash，所以Hash算法的设计就是从速度，效率，质量综合考虑来设计的

1
2
3
4
5
6
7
8
9
// 1，取hashCode
// 2，高位参与运算，这主要是让hash更离散，提高hash质量
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
 
 // 3，用位运算代替取模
 tab[i = (n - 1) & hash]

能用位运算代替取模的前提是n必须是2的整数次方，源码对table数组的size也确实做了限制，而且对reszie也有帮助，新位置 = 原位置 + 原size

1
2
3
4
5
6
7
8
9
10
// 位运算比一般的取模运算效率更高是因为取模需要做除法，触发器运算要多一个cpu时钟 
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashMap 线程安全

HashMap不是线程安全的，在resize时可能会出现环形链表，这时就死循环了。多线程下一般推荐使用ConcurrentHashMap。

初始变量

1
2
3
4
5
6
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;