众所周知, HashMap 内部是由一个 HashCode 的数组和链表组成 (jdk1.8 后, 当链表长度达到一定的阈值后, 会将链表转换成红黑树)
在初始化一个 HashMap 时, 默认的的 HashCode 数组的长度是 16, 为什么不可以是 5,10,13 这样的其他数呢?
- public V put(K key, V value) {
- if (key == null)
- return putForNullKey(value);
- // 计算 key 的 hashcode
- int hash = hash(key.hashCode());
- // 计算 hashcode 在数组里的位置
- 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;
- }
- // 用 key 的 hashcode 按位与 上数组长度
- static int indexFor(int h, int length) {
- // 任意一个数 & 15
- return h & (length-1);
- }
- void addEntry(int hash, K key, V value, int bucketIndex) {
- Entry<K,V> e = table[bucketIndex];
- table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
- if (size++>= threshold)
- // 数组长度的 2 倍
- resize(2 * table.length);
- }
Redis 中有 16384 个 slot, 分配的算法和 HashMap 计算数组下标的算法也是一样的, 有兴趣的可以看一下 Redis 的源码~
- /* 0x3FFF = 16383 , 也就是 16384-1, 与 hashmap 的 hash 算法不同, Redis 中用的是 crc16 算法, 但不管怎样, 最后也是按位与 length-1, 取值范围也一定是 0-16383 */
- return crc16(key,keylen) & 0x3FFF;
还有例如 Hadoop 中 MapReduce 时计算数据的分区, kafka 中计算存储的分区时, 用的是取余的算法.
例如, 分区总数是 3, 那么任何一个正整数对 3 取余, 结果一定是 0 1 2
来源: https://www.cnblogs.com/duoduotouhenying/p/10229842.html