Redis哈希表与jdk哈希表比较

Redis哈希表与jdk哈希表比较

Redis哈希表

// 字典
typedef struct dict {
  // 类型
  dictType *type;
  // 私有数据
  void *privdata;
  // 哈希表
  // 两个表，一个是使用的表，一个是供rehash使用的表
  dictht ht[2];
  //rehash索引
  // 默认为-1
  int rehashidx;
}
// Redis字典所使用的哈希表
typedef struct dictht {
  // 哈希表数组
  dictEntry **table;
  // 哈希表大小
  unsigned long size;
  // 哈希表大小掩码，用于计算索引值
  // 总等于size-1
  unsigned long sizemask;
  // 该哈希表已有节点的数量
  unsigned long used;
}dictht;

// 哈希表节点
typedef struct dictEntry {
  // 键
  void *key;
  // 值
  union{
    void *val;
    uint64_tu64;
    int64_ts64;
  } v;
  // 指向下个的哈希表节点，形成链表
  struct dictEntry *next;
}dictEntry;

• 结构。
  此哈希表是由数组+单链表实现。哈希算法是murmurHash算法，特点是能将有规律的key值计算出一个很好的随机数，并且计算速度也非常快。
• 哈希冲突
  由于此链表没有指向链尾的指针，为了速度考虑，总是将新节点添加到表头的位置（O（1））。

• rehash操作
  渐进式rehash，由于哈希表中保存的键值对有可能数量很大，一段时间内大量的计算和空间分配会对服务器造成很大的压力，甚至停止服务。故rehash是分多次、渐进式的将老table（oldTable）的键值对慢慢的rehash到新table（newTable）。步骤如下：
  1、为newTable分配空间，此时存在oldTable、newTable两表。
  2、更新rehashidx，将值设置为0，表示rehash开始。
  3、期间每次对字典进行操作时，程序执行指定的操作外，顺带将oldTable中下标等于rehashidx的键值对rehash到newTable。完成此操作后将rehashidx值+1。
  4、随着字典不断操作，最终oldTable所有的键值对都rehash到newTable中，此时rehashidx设置为-1，表示rehash操作完成。
  如下图所示。
  
  
  

jdk哈希表-HashMap

// hash表部分核心代码

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;
transient Node<K,V>[] table;// 数组节点
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
*******
}

• 结构
  java7及之前是由数组和单链表组成
  java8是由数组、单链表和二叉树。这里以java8为例。哈希算法(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
• 哈希冲突
  迭代到单链的表尾，并将键值对放入p.next = newNode(hash, key, value, null); 时间复杂度（O（n））。
• rehash（resize）操作
  1、使用一个容量更大的数组来代替已有的容量小的数组
  2、将原有Entry数组的元素拷贝到新的Entry数组里
• put操作
  ①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
  ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
  ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
  ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
  ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
  ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

各自优缺点

1. HashMap由于对链表size超过8采用二叉树结构，使得get操作随着激烈冲突导致变成一个类二叉树，时间复杂度为O(log(n))较redis的字典表O(n)，性能提升明显。
2. Redis的rehash由于采用渐进式的方式，对于大数据量下的rehash操作性能提升明显。这也是由于HashMap大部分用于临时且数据量不是特别大的数据，redis的hash用于存储避免大数据情况导致异常，双方的侧重点不一样。
3. Redis的单链表在冲突的情况下是从表头插入，时间复杂度为O(1)，而HashMap则为O(n)。