Redis

Hash
Hash数据结构底层实现为一个字典 dict，也是redisDb用来存储k-v的数据结构，当数据量比较小，或者单个元素比较小时，底层用ziplist存储，数据大小和元素数量阙值可以通过如下参数设置。
hash–max-ziplist-entries 512 //ziplist元素个数超过512，将改成hashtable编码
hash-max-ziplist-value 64 //单个元素大小超过64byte时，将改为hashtable编码
ziplist
hashtable跟redisDb用来存储k-v的数据结构一样。

java

HashMap
数据结构
数组+链表+（红黑树jdk>=8）
DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash表默认初始容量
MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量
DEFAULT_LOAD_FACTOR = 0.75f；默认加载因子
TREEIFY_THRESHOLD = 8；链表转红黑树阈值
UNTREEIFY_THRESHOLD = 6；红黑树转链表阈值
MIN_TREEIFY_CAPACITY = 64；链表转红黑树时hash表最小容量阈值，达不到优先扩容。

new HashMap():如果不写构造参数，默认大小是16
那么如果这地方写了new HashMap(11) 底层就给创建长度为11吗？不是，他是会有调整的，实际创建是16，那怎么转化的？
1.必须最接近size（11）
2.必须>=size
3.是2的指数次幂
size= 17, capacity=32
那么为什么是2的指数次幂呢？
底层：在计算索引的时候其实他内部用的不是%取余，而是用的位运算&，因为位运算比%效率高很多
计算索引：int i = indexFor(hash, table.length);
static int indexFor(int h, int length) {
// key.hashCode % table.lenth
return h & (table.lenth-1);
}
HashMap扩容，
当前hashmap存了多少element，size>=threshold
threshold扩容阈值 = capacity * 扩容阈值比率 0.75 = 16*0.75=12
扩容怎么扩？扩容为原来的2倍。
hash扩容，有个加载因子？loadfactor = 0.75为什么是0.75
牛顿二项式：基于空间与时间的折中考虑0.5（如果感兴趣，可以自己去网上看一下这个算法）
jdk1.7之前数据扩容后会要进行数据转移
代码

	void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) { 
                    e.hash = null == e.key ? 0 : hash(e.key);//再一次进行hash计算？
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

这种方式在转移过程存在问题，会出现转移后的数据链表成环的产生。

jdk1.8给其进行了优化，避免多线程下上面问题的产生。
引入红黑树！
只有等链表过长，阈值设置TREEIFY_THRESHOLD = 8，不是代表链表长度，链表长度>8,链表9的时候转红黑树
采用高低进行转移

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
    do {
        next = e.next;
        if ((e.hash & oldCap) == 0) {
            //yangguo.hashcode & 16 = 0，用低位指针
            if (loTail == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
        }
        else {
             //yangguo.hashcode & 16 》 0 高位指针
            if (hiTail == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
        }
    } while ((e = next) != null);
if (loTail != null) {
    loTail.next = null; 
    newTab[j] = loHead;，移到新的数组上的同样的index位置
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead; //index 3+16 = 19
}

完全绕开rehash，要满足高低位移动，必须数组容量是2的幂次方