不知如何分类
java

java-会用HashMap

一个问题引发的思考

如果确定只装载100个元素，new HashMap(?)多少是最佳的，why？
要解答这个问题，第一要知道HashMap的数据结构，第二再弄明白存取数据的逻辑。

1.首先，我是一个数组

HashMap本质上是一个数组，数组的每个元素是一个单链表或者红黑树，由0个或多个节点组成。
java源码中的定义如下：

1
transient Node<K,V>[] table;

1.1节点类Node<K,V>

Node类是HashMap的一个静态内部类，可以将其看成是一个独立的类，只是声明在HashMap类内部而已。下面是源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static class Node<K,V> implements Map.Entry<K,V> {//Entry是Map接口中的一个内部接口
    final int hash;//此节点的哈希值，同一个链表上的哈希值不一定相同
    final K key;//键，不能修改
    V value;//值
    Node<K,V> next;//指向下一个节点
 
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
 
    public final int hashCode() {//此Node类的hashCode方法
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
 
    public final V setValue(V newValue) {//重新设置节点Value，返回旧Value
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
 
    public final boolean equals(Object o) {//判断节点相等的方法，
        if (o == this)//同一个对象，返回true
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;//键和值都相等则返回true
        }
        return false;
    }
}

1.2为啥有链表还有树

为了提高查询效率，当链表的长度达到阈值的时候会自动将链表树形化，源码中的三个阈值常量如下：

1
2
3
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
  • TREEIFY_THRESHOLD 树形化阈值：当链表长度超过这个值的时候，将链表进行树形化改造
  • UNTREEIFY_THRESHOLD 链表化阈值：当节点数低于这个阈值，将红黑树改造成链表。这个值必须必树形化阈值小，避免频繁的转换。
  • MIN_TREEIFY_CAPACITY 最小树形化容量：当数组table的长度低于这个值，即使元素链表的长度超过树形化阈值，也不会进行树形化改造，而是对table进行扩容。这个值不能小于4*TREEIFY_THRESHOLD

    2.怎么进行数据的存取呢

    2.1hash方法

    拿到一个<Key,Value>，要存在table的哪个位置呢，这就需要用hash方法来决定了。。。
    从代码说起：
1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • key.hashCode()函数调用的是key键值类型自带的哈希函数（与HashMap的hashCode()函数不是同一个），它返回一个32位int类型的散列值。
  • 考虑到hash值得取值范围太大，不可能创建一个如此大的hash table，因此定位到table的位置只使用hash值的后几位（具体位数与table长度有关）。
  • 如果只取后几位，碰撞会比较严重，因此就有了扰动函数，将hash值右移16位（高16位移到低16位），再与自身亦或，得到的结果混合了原hash值得高位和低位，以此来加大低位的随机性。

2.2定位

最终得到的hash值，将由低位进行定位，定位操作如下：

1
2
n = tab.length
tab[(n - 1) & hash]

  • 数组长度必为2的整数次幂，因此(n-1)相当于低位掩码，与h进行与操作，保留h低位，掩盖高位。
  • 这里不做取余，是因为取余可能为负数（hashCode为负数的时候）
  • 不对取余进行模运算，是因为最大的整数Math.abs()会返回负值
  • 由此可知，对于HashMap的同一个链表的各个节点key值得hash值不一定相同（只是低位相同）

2.3扩容(resize)

默认容量是16

16是2的整数次幂的原因，在小数据量的情况下16比15或20更能减少key之间的碰撞，而加快查询的效率。

容量是15会怎样？

当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率（hash不均匀），降低了查询的效率！

所以，在存储大容量数据的时候，最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话，也会以大于且最接近指定值大小的2次幂来初始化的，代码如下(HashMap的构造方法中)： 

1
2
3
int capacity = 1;  
while (capacity < initialCapacity)   
    capacity <<= 1;  //乘以2
什么时候扩容&怎么扩容

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小length x loadFactor时，就会进行数组扩容，==loadFactor的默认值为0.75==，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16x0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以++如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能++。

回到开篇的问题

当有100个元素new HashMap(100), 但是理论上来讲new HashMap(128)更合适，不过上面已经说过，即使是100，hashmap也自动会将其设置为128。 但是new HashMap(128)还不是更合适的，因为0.75x100 < 100, 也就是说为了让0.75 x size > 100, 我们必须这样new HashMap(256)才最合适，既考虑了&的问题，也避免了resize的问题。

3.可以使用自定义的类作为key的类型吗

可以，但是必须改写key类型的hashcode与equals方法

首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。所以，hashcode与equals方法对于找到对应元素是两个关键方法。

Hashmap的key可以是任何类型的对象，例如User这种对象，为了保证两个具有相同属性的user的hashcode相同，我们就需要改写hashcode方法，比方把hashcode值的计算与User对象的id关联起来，那么只要user对象拥有相同id，那么他们的hashcode也能保持一致了，这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素，还需要用key的equals方法在对应位置的链表中找到需要的元素，所以只改写了hashcode方法是不够的，equals方法也是需要改写滴~当然啦，按正常思维逻辑，equals方法一般都会根据实际的业务内容来定义，例如根据user对象的id来判断两个user是否相等。

总结：

  • put操作时，根据key的hashcode()方法计算散列值，算法为高16位与低16位抑或之后，取table长度的后几位。因此，同一个table单位下，存储的元素key值可能不同。

  • get操作时，由于上述原因，需要根据key的equals()方法在链表或红黑树中进行查找。

  • 自定义类型作为key，需要重写hashcode方法和equals方法。