首先来看, 需要有怎样的特点: 在求取的过程中, key的每一点变化都会引起散列值的变化. 再细微的差别, 都需要不同的散列值来对应. 另一点是尽可能的足够分散. 在 Java中 实现的 hashCode()方法, 正是为了这个目的.
另一点是: % M, M的选择也尤为关键, 假设散列值为: 998 999 997 1999, 如果此时M选择10, 不难发现求余所得结果为 8, 9 , 7, 9. 有什么不对的吗?
很有问题, 因为高位无关性. 这样所得的结果会发现仅仅与个位数相关, 高位无关, 明显是不符合我们要求的. 那该怎么选择呢?
非2的素数. 比较符合我们的心理期望. 通过这样的方式就存储了对应的数组.
还有许多问题, 那就跟着Java的 HashMap的实现来一点点看, 究竟该怎么解决. 以及为什么这样解决.
HashMap注意:
读源码的时候, 我首先关注的是对这个类的解释, 有很多信息值得我们去发现.
容量和负载因子, 这两个与空间和时间相关. 当负载因子过大的时候, 会占用不必要的空间内存, 当负载因子过小的时候, 会导致时间上的消耗要更多一些. 在 HashMap中的默认取值, 负载因子为常数, 取的是 0.75.
在整个操作中, 我们需要始终维持 当前存量 / 负载因子 <= 容量.
当然, 也并不是说, 就不能够自由的调整负载因子, 如果查找时间对我们来说不是关注重点, 负载因子就可以调的大一点, 如果不在乎内存消耗, 就可以把这个值调整的更小一些.初始容量给的更大.
同样的无序性, 不过它的无序性更胜一筹, 不仅仅是大小无序, 另外存储的顺序也是完全得不到体现的.
不安全性, 线程不安全, 不多做解释, 需要线程安全的需要在创建的时候:
Map m = Collections.synchronizedMap(new HashMap(...));
当需要存储的数据量较大的时候, 在初始化的时候最好指定容量, 避免频繁的 rehash操作. 因为当每次容量变化的时候, 都需要重新计算转移数据, 比数组的复制更复杂.
属性
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;
transient Node
其余属性暂时不太理解原因. 一步步来看.
Node
static class Node<K,V> implements Map.Entry<K,V> { 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() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) 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; } return false; } }在这里, Node的hash值 由 value 和 key共同决定:
Objects.hashCode(key) ^ Objects.hashCode(value)
构造函数
在HashMap中, 提供了三个构造函数
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //这个参数 this.threshold = tableSizeFor(initialCapacity); } public HashMap(Map<? extends K, ? extends V> m);三个构造函数都是开放的, 在必要时,可以指定容量和 负载因子. 不过一般使用第二个就可以. 当不指定容量的时候, 为默认值16.
put()
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; /** *通过这种方式将高位bit位的变动传递到低位bit位, 只要有任何 *一位bit值改变, 都会在低16位上体现出来.原因还不是太清楚. */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {初始值默认设定为16;
Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;