Java HashMap loadfactor没有必要非是0.75
为什么hash常对 33/31 取模
作为整数，20世纪100以内自然数33和42曾在很长一段时间内无法找到表示为三个立方数和的解而成为神秘数字，33似乎也有一些与众不同，上述的DJB Hash 也叫 Time 33 hash，time 33就是乘33的意思。
unsigned int DJBHash(const char* str, unsigned int length){
unsigned int hash = 5381;
unsigned int i = 0;
for (i = 0; i < length; ++str, ++i)
{
hash = ((hash << 5) + hash) + (*str);
}
return hash;
}((hash << 5) + hash) 就是位操作实现的hash * 32+hash，即 hash * 33。
使用33是作者做过hash测试效果得到，我们这里看国内的1-1000之间作为乘数的测试，链接：，作者测试结果证实mod偶数或20以内的数据冲突率都很高，作者测试里四个数据效果：
编程规范牛书作者Kernighan 和 Ritchie 在《The C Programming Language》提出BKDR Hash，采用/
Java Hash
上面谈到Java String的hashCode实现，这里谈谈java其他hash
HashTable
Java中Hashtable就是使用除法散列法，Hashtable的table.size默认是11，即默认 % 11，resize时元素数量*2+1，但是初始size可以为指定值，也即指定初始2幂次时，hashtable可能散列的效果不好。
顺便提一下Netty中的IntObjectMap采用的是开放地址寻址法，hash策略就是简单的 key ^ (capacity - 1)，capacity是2的幂次。
Object.hashCode
HashMap/HashTable等都需要其hashCode方法，并且有一套hashcode/equals 规范，那么未重写时，即java Object默认hashCode方法怎么实现的呢，是内存地址的十六进制表示吗？
这篇文章里作者追踪源码并探讨几点，源码里多可见，笔者摘录下。
Object.hashCode是native方法，调用如下
// src/share/vm/prims/jvm.cpp
JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
JVMWrapper("JVM_IHashCode");
// as implemented in the classic virtual machine; return 0 if object is NULL
return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END
// 这里是作者简化过的伪码
// src/share/vm/runtime/synchronizer.cpp
intptr_t ObjectSynchronizer::FastHashCode (Thread * Self, oop obj) {
mark = monitor->header();
...
hash = mark->hash();
if (hash == 0) {
hash = get_next_hash(Self, obj);
...
}
...
return hash;
}
static inline intptr_t get_next_hash(Thread * Self, oop obj) {
intptr_t value = 0 ;
if (hashCode == 0) {
value = os::random() ;
} else
if (hashCode == 1) {
intptr_t addrBits = cast_from_oop(obj) >> 3 ;
value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
} else
if (hashCode == 2) {
value = 1 ; // for sensitivity testing
} else
if (hashCode == 3) {
value = ++GVars.hcSequence ;
} else
if (hashCode == 4) {
value = cast_from_oop(obj) ;
} else {
// Marsaglia's xor-shift scheme with thread-specific state
// This is probably the best overall implementation -- we'll
// likely make this the default in future releases.
unsigned t = Self->_hashStateX ;
t ^= (t << 11) ;
Self->_hashStateX = Self->_hashStateY ;
Self->_hashStateY = Self->_hashStateZ ;
Self->_hashStateZ = Self->_hashStateW ;
unsigned v = Self->_hashStateW ;
v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
Self->_hashStateW = v ;
value = v ;
}
...
return value;
}
product(intx, hashCode, 5,\
"(Unstable) select hashCode generation algorithm")
// src/share/vm/runtime/thread.cpp
_hashStateX = os::random() ;
_hashStateY = 842502087 ;
_hashStateZ = 0x8767 ; // (int)(3579807591LL & 0xffff) ;
_hashStateW = 273326509 ; 上述get_next_hash 提供了随机数、自增sequence、1、内存地址、Marsaglia’s xor-shift scheme with thread-specific state，默认就是 第五类实现，即含线程级别初始状态的hash码，可以看到 _hashStateX 就是一个os::random()的随机数，其他参数是恒定值，这也意味着Object.hashCode默认是随机的，也即如果你未重写hashCode，那么这个类即便每个属性都是一样的值，jvm重启之后/甚至在两个线程里new的两个对象，他们各自的hashCode是很可能不等的。
java Doc里
Whenever it is invoked on the same object more than once during an \
execution of a Java application, the hashCode method must \
consistently return the same integer...也提到了 during an execution of a Java application，即保证执行期间不变，没有明确指是始终不变，很多人忽略这点。
需要指出的是：
1） 上述，对象在调用一次hashCode之后，其hashCode缓存在其对象头字段里，以便之后使用，即mark->hash()。
2）通过jvm参数，-XX:hashCode=4 可以指定hashcode生成策略为内存地址。
但是为何hashcode默认要随机数？
让我们看一段历史，虽然二者不一定相关。
如果你使用Python 3.2以上，那么shell里运行hash(‘www’)后退出再运行 hash(‘www’)，就会发现两次hash值不一样，这是为了解决python 问题,具体参考：，文末链接是各语言。
这个问题曾经在PHP服务较明显，而Tomcat/jettty等也出现过，笔者刚工作时就曾经历过Tomcat因此升级，这里是讨论：，，，原理就是已知tomcat这些通过hashmap解析用户post的参数（request.getparameter），那么用户会构造一个表单，比如含有一万个字段，他们都会hash到同一个键上，即查询时退化为链表查询了，导致在处理上比较损耗CPU，这点据说对PHP服务影响巨大，CPU观测到飙升。Tomcat该CVE解决就是设置参数限制用户的表单字段数量。
需要指出的是，除了Object.hashCode，JDK 1.7(应该是2012年2月之后的版本，早期1.7版本是没有的，因版本问题，下面代码是笔者网上找的jdk代码)的HashMap似乎也做了改进，在计算HashMap的加入了hashSeed随机，hashSeed会在vm启动时通过random初始化，而对于String类sun.misc.Hashing.stringHash32则采用 murmur3_32，该murmur算法使用时间戳作为随机种子。
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);
return h ^ (h >>> 7) ^ (h >>> 4);
}Java HashMap
不过，随机hash可能不符合部分人的理念，JDK 8中HashMap就去掉了随机hash，String的hashcode永远一样，链表解决冲突改为红黑树，避免hash攻击。
所以HashMap的hash策略相比1.7就简略许多：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}1.7中String类曾使用murmurhash计算hashcode，其他则会对其进行20/12/7/4位的rotate，1.8中这些都不存在了，并且只一次性rotate16位，这样保证高低16位均可再次参与hash，如果论1.8的放大效应应该不如1.7，但是大大减少了rotate和异或操作次数，而且有红黑树兜底冲突。
在计算hash这步应该会快些，但1.8中红黑树带来代码复杂性，且当该槽退化为红黑树后，转换为treenode时，进行查找比较时，对于”class C implements Comparable“存在反射调用的性能损耗，很难说哪个快，需要具体测试结果，并考虑hash冲突次数情况来比较试验。
正是由于这一点，JDK 1.8 的hash关于红黑树其实是两个改进：1)当槽位冲突超过8(含)时链表升级为红黑树，2）resize后，如果槽位冲突小于6，但是红黑树，此时会降级为链表。
上面其实也意味着当hashmap size较小如64，1.8中参与有效hash的位通常不如1.7的多。
为何是超8个才升级为红黑树
备注里写的清楚了
* Because TreeNodes are about twice the size of regular nodes,
* ...
* Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
...笔者不会涉及红黑实现细节，只讨论部分问题。
上述可知：
1, TreeNodes 重量级，耗费空间
2，hash冲突超过8个的情况概率可以做到非常小到6/10^8机会，
也就是说，该版本里JDK设计者并不希望用户的hashmap出现红黑树！
引入红黑树冲突解决是作为极端情况(DOS)下的兜底方案，而不是一种对Hashmap自身功能上的优化，笔者不确定1.8的HashMap是否比1.7快(单线程)，虽然hash变得简单高效，但本身操作就足够敏感，相信科学的压测结果未必能足够证明二者性能之间的差异(如hash的key为String时，string的长度影响get的性能)。不过，笔者可以确认的是，“Java 8 引入红黑树处理冲突提升了HashMap的性能”，这种说法是完全不对的，Java 8 HahsMap即便性能有提升也不会直接和链表冲突变为红黑树相关。
正如作者在上述写的选择8的原因是因为这样使得链表升级TreeNode情况的可能性足够小，这里又怎么去考虑性能呢，更别说链表超过8个转换为树是否更高效了。
至于loadfactor为0.75纯粹是经验值（可能就是0.5和1.0取中间），没有什么好探讨的，笔者的疑惑是“Ideally, under random hashCodes, the frequency of nodes in bins follows”，毕竟下文得出选用8作为临界的原因就是“出现K次同一个碰撞”符合泊松分布，但首先确定的一点是作者的公式前提是假设loadfactor为0.5，如果强行认为泊松分布没有问题，但是需要解释lambda为何0.5。
如果按注释理解，笔者猜测作者可能是把K数丢到N桶作为二项分布，或者说作者可能是把N个桶作为一个个的单位时间，而把数丢到N桶看成是每个时间内概率性到达一个数，这个概率是0.5，当把时间无限长，显然这个模型里每个时间K次到达本身就是泊松分布，把lambda带入0.5就得到作者的
换句话说，将n/2的数随机放入n个桶内，约0.60653066的的量是空桶，0.30326533的量含有1个，0.07581633的量含有2个…这个结果有点意外，但是如果代码试验记录函数关系，猜测可能是符合这个图形的(文末笔者用Redis测试了一下，结果是比较符合这个结论的)。
为何hash槽数是2的幂次
不同于hashtable，hashmap的槽数始终是2的幂次，Redis也是如此。
读者可能已经知道HashMap采用这种设计，主要是为了高效取模
笔者认为有缺陷但不矛盾，首先 取模前的 hash值有做过高低位的一次位操作，并且在此之前也有几轮位散列，这个过程比较接近 乘法散列法，只是此时m为2的幂次的倒数。
loadfactor 0.75 是否合理
笔者认为合理，但是有时候可以不遵守。
loadfactor是衡量hash表饱和度的指数，过大也意味着hash冲突的概率很大，当超过0.75时，HashMap进行扩容(resize)，槽数翻倍，读者可能已经在Java doc中看到推荐0.75，以及其他博客里认为的超过0.75性能就有损耗，不推荐。
而Java中，hashmap要素就是希望冲突尽量少，将表操作维持在 O(1)时间，但是，超过0.75时性能损耗有多少呢？
上文我们分析了采用链表式的简单一致hash表，理论上一次成功/不成功的查找耗时均为 O(1+a)，a为装载因子，也就是说，loadfactor设为3的时候查询性能是之前的2.9倍，但考虑到hash操作可能是耗时重点，这个值会比2.9小。
笔者没有进行严格的JMH测试，分别用0.75和4作为loadfactor插入12万条KV数据对后，简单的进行16轮get测试，在笔者的mac电脑上时间比在1.4-2.8之间，但是占用空间4是32768条，0.75是262144条，仅为其1/8。
对于内存消耗频繁/GC频繁的应用来说，如果能接受hashmap的查询耗时损耗，笔者认为这可能是非常值得的。
当然，上述还有待笔者更多的性能测试数据，简单的循环跑可能有干扰。
Redis的loadfactor、hash相关
Redis本身有Hash类型的数据结构之外，redis数据库实现也是一个Hash表，即dict，存储了redis所有的KV对，其哈希策略早期是随机的murmur2，后来或许是受SipHash作者的murmur存在hash DOS问题，策略改为SipHash了。
dict用链表解决哈希冲突，其loadfactor默认大于1才开始resize(dict_can_resize固定1)，可以一直持续增加到5后再强行resize(dict_force_resize_ratio固定5)。
即redis认为自己的数据量大于dict的槽数是允许的，而Java HashMap建议槽数大于数据量。
当然Redis Hash也得益于其hashtable不仅可以扩张，而且可收缩，支持一种渐进式rehash机制，即其hashtable逻辑上有两个hashtable组成(当rehash时)，可同时并用，并且空闲时迁移，直到rehash结束后，其中一个清空。
可以看到一个redisDb就是一个dict，dict主要就是dictht ht[2]，2个大的hash表(dictEntry)引用，
/* Redis database representation. There are multiple databases identified
* by integers from 0 (the default database) up to the max configured
* database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
dict *blocking_keys; /* Keys with clients waiting for data (BLPOP)*/
dict *ready_keys; /* Blocked keys that received a PUSH */
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
int id; /* Database ID */
long long avg_ttl; /* Average TTL, just for stats */
unsigned long expires_cursor; /* Cursor of the active expire cycle. */
list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
typedef struct dictType {
uint64_t (*hashFunction)(const void *key);
void *(*keyDup)(void *privdata, const void *key);
void *(*valDup)(void *privdata, const void *obj);
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
void (*keyDestructor)(void *privdata, void *key);
void (*valDestructor)(void *privdata, void *obj);
} dictType;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;4.0后，redis大部分dictType的hashFunction都是dictSdsHash(部分dictObjHash)，他们都属于dictGenHashFunction，即对应siphash实现。
Redis的HyperLogLog目前还是用MurmurHahs进行哈希。
我们知道Antirez，redis get操作大概在12万/s左右，那么Redis的dict查找性能有多快呢？验证需要深入代码，不过我们可以看另一个数据，就是pipeline测试，
Redis resize过程还有许多内容，比如scan的实现，能看到作者是非常的善于用心，不走寻常路思维，不过本文不进一步讨论。
redis hashtable的KV分布的问题
笔者用Redis模拟，并非Java，分别用随机产生53万/105万万数据测试下来接近备注里的分布。注意：
1）在插入完成后，需要等几秒redis完成rehash再debug htstats。
2）下述随机数的数量选择在2的幂次附近，是为了让redis进行rehash临界，满足 0.5的负载，比如产生106万是为了近可能未产生超1048576个从而使得redis rehash。
# 产生529276个随机数/1048576个槽
➜ ~ git: bin/redis-benchmark -q -n 530000 -P 16 -r 100000000 set key:__rand_int__ __rand_int__
set key:__rand_int__ __rand_int__: 398009.94 requests per second
# 对应 hashtable
127.0.0.1:6379> debug htstats 0
[Dictionary HT]
Hash table 0 stats (main hash table):
table size: 1048576
number of elements: 529276
different slots: 415816
max chain length: 7
avg chain length (counted): 1.27
avg chain length (computed): 1.27
Chain length distribution:
0: 632760 (60.34%)
1: 319982 (30.52%)
2: 80377 (7.67%)
3: 13508 (1.29%)
4: 1748 (0.17%)
5: 183 (0.02%)
6: 17 (0.00%)
7: 1 (0.00%)
[Expires HT]
# 产生1055783个随机数/2097152个槽
➜ ~ git: bin/redis-benchmark -q -n 1060000 -P 16 -r 100000000 set key:__rand_int__ __rand_int__
127.0.0.1:6379> debug htstats 0
[Dictionary HT]
Hash table 0 stats (main hash table):
table size: 2097152
number of elements: 1055783
different slots: 829655
max chain length: 7
avg chain length (counted): 1.27
avg chain length (computed): 1.27
Chain length distribution:
0: 1267497 (60.44%)
1: 638693 (30.46%)
2: 160040 (7.63%)
3: 27052 (1.29%)
4: 3531 (0.17%)
5: 307 (0.01%)
6: 29 (0.00%)
7: 3 (0.00%)
[Expires HT]可以看到当负载因子接近0.5时，上述分布和java HashMap给出的理论分布比较符合的。