logo
ZhangJerry
banner
NEWS LETTER

Redis源码分析（二）字典

Scroll down

[toc]

一、基础结构对比

数据结构定义

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 底层数组
    transient Node<K,V>[] table;
    // 元素数量
    transient int size;
    // 修改次数，用于快速失败机制
    transient int modCount;
    // 扩容阈值
    int threshold;
    // 负载因子
    final float loadFactor;
    
    // 基本节点类型
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    
    // 红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;
        // ...
    }
}

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef struct dict {
    dictType *type;       // 哈希表类型，包含各种操作函数指针
    void *privdata;       // 私有数据
    dictht ht[2];         // 两个哈希表，支持rehash
    int rehashidx;        // rehash索引，-1表示没有进行rehash
    int iterators;        // 安全迭代器计数
} dict;

typedef struct dictht {
    dictEntry **table;    // 哈希表数组
    unsigned long size;   // 哈希表大小
    unsigned long sizemask; // 掩码，等于size-1
    unsigned long used;   // 哈希表中已有节点数量
} dictht;

typedef struct dictEntry {
    void *key;            // 键
    union {               // 值可以是多种类型
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 下一个节点
} dictEntry;

主要区别与设计思路

  1. 多态实现方式：

    • Java：使用泛型和继承实现多态
    • Redis：使用函数指针（dictType）实现不同类型的操作

  2. 哈希表数量：

    • Java：仅一个哈希表数组
    • Redis：两个哈希表，用于渐进式rehash

    设计原因：Redis作为数据库需要保持稳定响应时间，一次性rehash可能导致较长停顿

  3. 节点结构：

    • Java：有普通节点和树节点两种
    • Redis：仅有一种节点类型

    设计原因：Java HashMap追求在高冲突下的性能保证，而Redis通过控制负载因子和良好的哈希函数减少冲突

二、关键操作API对比

初始化

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 默认构造函数
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
}

// 指定初始容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 指定初始容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
    // 参数检查
    if (initialCapacity < 0) throw new IllegalArgumentException("...");
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("...");
    
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); // 计算为大于initialCapacity的最小2的幂
}

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 创建字典
dict *dictCreate(dictType *type, void *privDataPtr) {
    dict *d = zmalloc(sizeof(*d));
    _dictInit(d, type, privDataPtr);
    return d;
}

// 初始化字典
int _dictInit(dict *d, dictType *type, void *privDataPtr) {
    _dictReset(&d->ht[0]); // 重置第一个哈希表
    _dictReset(&d->ht[1]); // 重置第二个哈希表
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;    // 表示没有进行rehash
    d->iterators = 0;
    return DICT_OK;
}

差异分析：

  • Java提供多个构造函数满足不同初始化需求，Redis采用工厂方法模式
  • Java直接在构造时设定扩容阈值，Redis延迟到实际需要扩容时
  • Java的负载因子作为实例变量存储，Redis使用全局变量控制

添加元素

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判断是否需要初始化表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 计算索引并判断槽位是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 第一个节点就是要找的key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 检查是否为树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 遍历链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 检查是否需要树化
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 更新已存在的key的值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 增加修改计数
    ++modCount;
    // 检查是否需要扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int dictAdd(dict *d, void *key, void *val) {
    dictEntry *entry = dictAddRaw(d, key);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key) {
    int index;
    dictEntry *entry;
    dictht *ht;
    
    // 如果正在rehash，执行一步渐进式rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 获取新元素的索引，如果key已存在则返回-1
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;
    
    // 选择使用哪个哈希表（rehash时用ht[1]，否则用ht[0]）
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    
    // 头插法将新节点插入链表
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    
    // 设置键
    dictSetKey(d, entry, key);
    return entry;
}

差异分析：

  1. 查找与插入合并：

    • Java中先查找后插入，一次遍历
    • Redis先检查键是否存在，然后分开执行插入操作

  2. 扩容触发：

    • Java在添加元素后检查是否需要扩容
    • Redis在_dictKeyIndex函数中检查是否需要扩容

  3. 冲突处理：

    • Java在链表长度超过阈值时转为红黑树
    • Redis始终使用链表，但会在每次操作时执行一步rehash

  4. 错误处理：

    • Java通过返回旧值表示替换，null表示新增
    • Redis通过返回状态码（DICT_OK/DICT_ERR）表示操作成功/失败

查找元素

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 检查表是否为空，并计算索引
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // 检查第一个节点
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
            
        // 遍历后续节点
        if ((e = first.next) != null) {
            // 如果是树节点，使用树查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
            // 否则遍历链表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
dictEntry *dictFind(dict *d, const void *key) {
    dictEntry *he;
    unsigned int h, idx, table;
    
    // 空表直接返回NULL
    if (d->ht[0].used + d->ht[1].used == 0) return NULL;
    
    // 如果正在rehash，执行一步渐进式rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 计算哈希值
    h = dictHashKey(d, key);
    
    // 在两个表中查找
    for (table = 0; table <= 1; table++) {
        // 计算索引
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        
        // 遍历链表查找
        while (he) {
            if (key == he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        
        // 如果没有进行rehash，无需检查第二个表
        if (!dictIsRehashing(d)) break;
    }
    return NULL;
}

void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;
    
    he = dictFind(d, key);
    return he ? dictGetVal(he) : NULL;
}

差异分析：

  1. 查找策略：

    • Java先检查首节点，然后根据节点类型采用不同查找方法（链表遍历或树查找）
    • Redis在所有情况下都使用简单的链表遍历

  2. rehash考虑：

    • Java查找不触发任何rehash
    • Redis在查找前执行一步渐进式rehash，并在两个哈希表中查找

  3. 键比较：

    • Java使用equals方法和==操作符组合判断
    • Redis使用dictCompareKeys回调函数，支持自定义比较

删除元素

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                          boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    
    // 定位节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        
        Node<K,V> node = null, e; K k; V v;
        
        // 检查首节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 树节点处理
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 链表遍历
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 找到节点后的删除操作
        if (node != null && (!matchValue || (v = node.value) == value ||
                            (value != null && value.equals(v)))) {
            // 树节点移除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 首节点移除
            else if (node == p)
                tab[index] = node.next;
            // 非首节点移除
            else
                p.next = node.next;
                
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht, key, 0);
}

static int dictGenericDelete(dict *d, const void *key, int nofree) {
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;
    
    // 空表检查
    if (d->ht[0].size == 0) return DICT_ERR;
    
    // 如果正在rehash，执行一步渐进式rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 计算哈希值
    h = dictHashKey(d, key);
    
    // 在两个表中查找
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        
        // 遍历链表
        while(he) {
            if (key == he->key || dictCompareKeys(d, key, he->key)) {
                // 从链表中删除节点
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                    
                // 释放节点内存
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        
        // 如果没有进行rehash，无需检查第二个表
        if (!dictIsRehashing(d)) break;
    }
    return DICT_ERR;
}

差异分析：

  1. 查找策略：

    • Java根据节点类型（普通/树）采用不同查找方法
    • Redis仅使用简单链表遍历

  2. 返回值：

    • Java返回被删除的节点或null
    • Redis返回操作状态码（DICT_OK/DICT_ERR）

  3. 内存管理：

    • Java依赖GC回收内存
    • Redis有nofree参数控制是否释放键值内存，并显式调用zfree释放节点

  4. 额外操作：

    • Java有afterNodeRemoval回调供LinkedHashMap等子类使用
    • Redis在删除时也会执行渐进式rehash

扩容/重哈希操作

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 计算新容量和阈值
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值翻倍
    }
    else if (oldThr > 0) // 初始容量在阈值中
        newCap = oldThr;
    else { // 无参构造，使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                 (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    // 创建新表
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 将旧表数据迁移到新表
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 使用"拆分桶"技术优化迁移
                    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) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 高位桶
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int dictExpand(dict *d, unsigned long size) {
    dictht n; // 新哈希表
    unsigned long realsize = _dictNextPower(size);
    
    // 检查是否正在rehash或size太小
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
        
    // 如果新大小与当前大小相同，无需扩容
    if (realsize == d->ht[0].size) return DICT_ERR;
    
    // 分配新哈希表
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    
    // 如果是首次初始化
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }
    
    // 准备渐进式rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

// 渐进式rehash
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; // 最大允许访问的空桶数
    
    if (!dictIsRehashing(d)) return 0;
    
    // 执行n步rehash
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        
        // 找到一个非空桶
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        
        // 获取该桶的链表头
        de = d->ht[0].table[d->rehashidx];
        
        // 将该桶所有节点迁移到新表
        while(de) {
            unsigned int h;
            
            nextde = de->next; // 保存下一节点
            
            // 计算新表索引
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            
            // 头插法插入新表
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            
            de = nextde;
        }
        
        // 清空旧表该桶
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    
    // 检查是否完成所有rehash
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    
    // 还有更多要rehash
    return 1;
}

差异分析：

  1. 扩容时机：

    • Java在put操作后检查是否需要扩容
    • Redis在多个操作中检查，但引入了dict_can_resize控制扩容行为

  2. 执行方式：

    • Java一次性完成所有迁移工作
    • Redis采用渐进式rehash，将迁移工作分散到多个操作中

  3. 空间分配：

    • Java直接使用新表替换旧表
    • Redis同时维护两个表，逐步将旧表元素迁移到新表

  4. 优化策略：

    • Java使用”拆分桶”技术，减少链表遍历
    • Redis通过限制每次执行的步数和空桶访问数控制性能

三、性能设计考量

哈希函数设计

Java HashMap

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 位扩散：将高16位XOR到低16位，减少在小表上的冲突
  • null处理：显式支持null键，返回0作为哈希值

Redis字典

Redis提供多种哈希函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Thomas Wang's 32位整数哈希
unsigned int dictIntHashFunction(unsigned int key) {
    key += ~(key << 15);
    key ^=  (key >> 10);
    key +=  (key << 3);
    key ^=  (key >> 6);
    key += ~(key << 11);
    key ^=  (key >> 16);
    return key;
}

// MurmurHash2字符串哈希
unsigned int dictGenHashFunction(const void *key, int len) {
    /* MurmurHash2算法实现 */
}

// 大小写不敏感的哈希（基于djb算法）
unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) {
    unsigned int hash = (unsigned int)dict_hash_function_seed;
    while (len--)
        hash = ((hash << 5) + hash) + (tolower(*buf++)); /* hash * 33 + c */
    return hash;
}

差异分析：

  • Java依赖对象的hashCode方法，然后进行位扩散
  • Redis针对不同数据类型提供专用哈希函数，更好地控制分布

冲突处理

Java HashMap

  • 链表→红黑树转换：链表长度超过TREEIFY_THRESHOLD(8)时，转换为红黑树
  • 红黑树→链表转换：树节点数量小于UNTREEIFY_THRESHOLD(6)时，转回链表
  • 最小树化容量：表容量小于MIN_TREEIFY_CAPACITY(64)时先扩容而不树化

Redis字典

  • 纯链表法：始终使用链表解决冲突
  • 渐进式rehash：通过增量rehash控制链表长度
  • 强制扩容比例：当元素/桶比例超过dict_force_resize_ratio(5)时强制扩容

设计考量：

  • Java的树化处理适合存在热点key的场景，保证最坏情况O(log n)性能
  • Redis通过控制负载因子和渐进式rehash，避免长链表出现，适合均匀分布场景

迭代器设计

Java HashMap

  • Fail-Fast迭代器：检测modCount变化，发现结构变化立即抛出ConcurrentModificationException
  • Spliterator支持：提供并行迭代支持

Redis字典

  • 安全迭代器：dictGetSafeIterator增加iterators计数，暂停rehash
  • 非安全迭代器：dictGetIterator用指纹机制检测迭代过程中的修改
  • 渐进式迭代：dictScan支持增量式迭代大字典

设计考量：

  • Java侧重并发场景下的错误检测
  • Redis关注大数据量迭代的性能和内存一致性

四、内存管理与性能权衡

内存布局

Java HashMap

  • 对象模型：每个键值对都是独立的Node对象，额外引用开销
  • 数组扩容：创建新数组并迁移，暂时占用双倍内存
  • 树节点：TreeNode包含更多指针，内存占用更大

Redis字典

  • 紧凑布局：直接使用指针引用键值，减少封装开销
  • 双表存储：渐进式rehash期间同时维护两个表，额外空间开销
  • 单一节点类型：所有节点结构相同，无特殊处理

时间-空间权衡

Java HashMap

  • 一次性rehash：牺牲单次操作延迟，换取整体更少的内存占用
  • 树化优化：牺牲空间（树节点更大），换取查找性能（从O(n)到O(log n)）
  • 懒加载：首次使用时才初始化table数组，节省初始内存

Redis字典

  • 渐进式rehash：牺牲持续时间内的额外内存占用，换取操作的平均延迟降低
  • 负载因子控制：通过dict_force_resize_ratio控制扩容时机，平衡内存使用和性能
  • 可禁用rehash：dictDisableResize()允许在特定场景（如fork子进程时）禁用扩容

权衡分析：

  • Java HashMap更注重通用性能和内存利用率的平衡
  • Redis字典更关注操作延迟的一致性，适合实时系统需求

五、线程安全考虑

Java HashMap

  • 非线程安全设计：HashMap本身不是线程安全的
  • 外部同步：提供Collections.synchronizedMap进行包装
  • 并发替代品：提供ConcurrentHashMap作为线程安全替代
  • 快速失败机制：通过modCount检测并发修改
    1
    2
    3
    // 并发修改检测
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();

Redis字典

  • 单线程模型：Redis主要是单线程架构，字典操作天然线程安全
  • RDB持久化保护：在fork子进程时可禁用rehash
    1
    2
    3
    4
    5
    6
    7
    8
    // 可控制的rehash开关
    void dictDisableResize(void) {
        dict_can_resize = 0;
    }

    void dictEnableResize(void) {
        dict_can_resize = 1;
    }
  • 指纹机制：使用dictFingerprint()检测字典的非法修改

设计理念对比：

  • Java HashMap将线程安全问题委托给外部处理或使用专门的并发版本
  • Redis字典不直接处理线程安全，而是适应Redis的单线程模型和fork场景

六、特殊功能比较

随机访问

Java HashMap

  • 不直接支持随机元素访问

Redis字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 随机返回一个键值对
dictEntry *dictGetRandomKey(dict *d) {
    dictEntry *he, *orighe;
    unsigned int h;
    int listlen, listele;
    
    // 空表检查
    if (dictSize(d) == 0) return NULL;
    
    // 如果正在rehash，执行一步渐进式rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 随机选择一个非空桶
    if (dictIsRehashing(d)) {
        do {
            h = d->rehashidx + (random() % (d->ht[0].size +
                                          d->ht[1].size -
                                          d->rehashidx));
            he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
                                      d->ht[0].table[h];
        } while(he == NULL);
    } else {
        do {
            h = random() & d->ht[0].sizemask;
            he = d->ht[0].table[h];
        } while(he == NULL);
    }
    
    // 计算链表长度并随机选择节点
    listlen = 0;
    orighe = he;
    while(he) {
        he = he->next;
        listlen++;
    }
    listele = random() % listlen;
    he = orighe;
    while(listele--) he = he->next;
    return he;
}

设计原因：

  • Redis作为数据库和缓存系统需要支持抽样操作和过期键淘汰
  • Java HashMap作为通用数据结构无此需求

批量操作

Java HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 批量添加
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 预先扩容
        if (table == null) {
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
            
        // 批量插入
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

Redis字典

  • 没有专门的批量操作API
  • 通过单个操作的增量rehash实现平滑批量处理

设计考量：

  • Java HashMap支持批量操作，但仍可能因resize产生延迟峰值
  • Redis通过渐进式rehash将批量操作的成本分摊，更适合实时系统

七、哈希冲突处理机制详解

Java HashMap的树化机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 树化阈值
static final int TREEIFY_THRESHOLD = 8;

// 将链表转化为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 如果表太小，优先扩容而非树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 将链表节点转换为树节点
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        
        // 构建红黑树结构
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

// TreeNode实现了红黑树的各种操作
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // 双向链表支持
    boolean red;
    
    // 红黑树查找
    final TreeNode<K,V> getTreeNode(int h, Object k) {
        return ((parent != null) ? root() : this).find(h, k, null);
    }
    
    // 查找算法，结合哈希值和比较器
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this;
        do {
            int ph, dir; K pk; TreeNode<K,V> pl, pr, q;
            if ((ph = p.hash) > h)
                p = pl = p.left;
            else if (ph < h)
                p = pr = p.right;
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            else if (pl == null)
                p = pr;
            else if (pr == null)
                p = pl;
            else if ((kc != null || (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;
        } while (p != null);
        return null;
    }
}

Redis的渐进式rehash机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// 执行n步rehash
int dictRehash(dict *d, int n) {
    int empty_visits = n*10;
    if (!dictIsRehashing(d)) return 0;
    
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        
        // 找到非空桶
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        
        // 获取索引位置的链表头
        de = d->ht[0].table[d->rehashidx];
        
        // 迁移整个链表
        while(de) {
            unsigned int h;
            nextde = de->next;
            
            // 计算新哈希表中的位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        
        // 清空旧表该位置
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }
    
    // 检查是否完成所有rehash
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }
    
    return 1;
}

// 在其他操作中触发rehash
static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d, 1);
}

设计哲学对比：

  1. Java的方法：

    • 自适应结构：根据实际冲突情况动态切换链表/树结构
    • 优化热点：通过红黑树优化热点数据访问，保证最坏情况性能
    • 一次性成本：扩容时承担一次性较大成本，但保持结构简单

  2. Redis的方法：

    • 增量设计：将rehash分散到多个操作中
    • 延迟均衡：避免单次操作延迟峰值，保证实时性
    • 双表机制：通过双表设计支持增量rehash，以空间换时间

八、总结与实践建议

设计决策对比

特性 Java HashMap Redis 字典 影响
冲突解决 链表 + 红黑树 仅链表 Java在高冲突情况下性能更稳定
扩容方式 一次性 渐进式 Redis操作延迟更一致
负载因子 默认0.75 可调整，强制阈值为5 Java空间效率更高
内存分配 连续数组 两个哈希表 Redis在rehash期间内存占用更高
随机访问 不支持 支持 Redis更适合抽样操作
线程安全 非线程安全 基于单线程模型 两者都需要外部同步机制
代码复杂度 较高（树操作） 中等（双表管理） Java实现更复杂但处理极端情况更佳

适用场景建议

Java HashMap适合：

  1. 通用存储：作为通用键值存储结构
  2. 内存敏感：对内存使用效率要求高的场景
  3. 不均匀分布：键的分布不均匀，存在热点数据的场景
  4. 批量操作：可接受偶尔的延迟峰值

Redis 字典适合：

  1. 实时系统：需要稳定、可预测延迟的场景
  2. 持续高频操作：需要避免操作阻塞的高吞吐系统
  3. 数据库基础结构：作为数据库核心组件，需要特殊控制
  4. 大规模数据：处理大规模数据集，需要平滑扩容

设计启示

  1. 平衡与取舍：

    • Java选择了”大多数情况效率高，最坏情况有保障”的策略
    • Redis选择了”延迟稳定、可控制”的策略

  2. 适应使用环境：

    • Java HashMap适应了JVM和通用编程模式
    • Redis字典适应了数据库和缓存系统的特殊需求

  3. 演化路径：

    • Java HashMap从JDK 1.8开始引入树化机制，是对早期版本的优化
    • Redis字典设计初期就考虑了渐进式rehash，体现了实时系统设计思想

  4. 工程智慧：

    • 两种实现都不是”完美”的，而是在各自约束下的最优解
    • 充分考虑了实际使用场景、性能特征和工程复杂度

九、源码深入剖析

哈希函数的设计哲学

Java HashMap的位扩散设计

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这种设计将高16位的信息混入低16位，主要考虑：

  1. 表大小影响：当表较小时，只有低位参与索引计算 (n-1) & hash
  2. 分布改善：通过高低位异或，让高位信息也能影响到最终索引
  3. 计算效率：比完整哈希算法开销小，但能显著改善分布

Redis多种哈希函数

Redis提供多种哈希函数以适应不同类型的键：

  1. 整数哈希：Thomas Wang算法，快速处理整数键
  2. 字符串哈希：MurmurHash2，均匀分布且计算高效
  3. 不区分大小写哈希：基于djb算法的变种，适合不区分大小写的字符串

扩容和缩容的精细控制

Java HashMap的扩容策略

1
2
3
4
5
6
7
8
9
10
11
12
13
// 当前大小翻倍
newCap = oldCap << 1;

// 表大小始终是2的幂
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap不主动收缩，只会在负载超过阈值时扩容。这种策略有以下考虑：

  1. 避免频繁扩缩容导致的性能抖动
  2. 用空间换时间，保持查询效率
  3. 简化实现复杂度

Redis的扩缩容控制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 扩容检查
static int _dictExpandIfNeeded(dict *d) {
    if (dictIsRehashing(d)) return DICT_OK;
    
    if (d->ht[0].size == 0)
        return dictExpand(d, DICT_HT_INITIAL_SIZE);
        
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

Redis支持扩容和收缩：

  1. 可通过全局开关控制是否允许重新调整大小
  2. 即使禁用了正常调整大小，也有强制阈值保证极端情况下的性能
  3. 收缩时机通常由上层应用触发，如键过期等场景

内存布局和缓存效率

Java HashMap的内存特性

  • 连续存储：桶数组是连续的，具有良好的缓存局部性
  • 节点分散：链表/树节点在堆上分散，缓存不友好
  • 装箱开销：泛型实现导致基本类型需要装箱，增加内存开销

Redis字典的内存特性

  • 指针直接性：直接使用指针而非对象封装，减少间接寻址
  • 双表交替：rehash期间的双表可能导致缓存未命中率增加
  • 键值灵活性：通过union结构支持不同类型的值存储，减少额外封装

十、实际应用场景示例

场景1：高频读取、低频写入

Java HashMap的表现

1
2
3
4
5
6
7
8
9
10
11
12
// 初始化足够大的容量以避免扩容
Map<String, Data> cache = new HashMap<>(10000, 0.75f);

// 批量预加载
for (Data item : preloadData) {
    cache.put(item.getKey(), item);
}

// 高频读取
public Data getData(String key) {
    return cache.get(key);
}

优势：一旦预加载完成，读取操作非常高效，特别是在数据分布不均时

场景2：实时交易系统

Redis字典的表现

1
2
3
4
5
6
7
8
// 在处理交易期间临时禁用rehash
dictDisableResize();

// 交易处理
processTransaction();

// 处理完成后恢复rehash
dictEnableResize();

优势：可精确控制延迟敏感期内的字典行为，保证操作延迟的稳定性

场景3：内存优化

Java HashMap的表现

1
2
// 使用computeIfAbsent优化内存
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

优势：函数式API可以延迟创建对象，减少内存占用

Redis字典的表现

1
// 使用压缩链表等特殊编码（Redis上层实现）

优势：Redis可对特定数据类型使用特殊编码，极大节省内存

结论

Java HashMap和Redis字典实现都是哈希表的杰出案例，但针对不同应用场景做了专门优化：

  • Java HashMap 更注重通用性、最坏情况保证和整体内存效率，适合作为通用集合类型
  • Redis字典 更注重操作延迟的一致性、实时性和可控性，适合作为数据库核心组件
其他文章
cover
随笔
在不确定性的迷雾中航行：拥抱复杂性，走向谦逊与务实
  • 25/05/03
  • 13:26
cover
源码分析
Redis源码分析（一）跳表
  • 25/05/03
  • 13:23
© 2024 - 2025 Jerry
由 Hexo 驱动 v7.3.0 主题 - Async v2.2.4
目录导航 置顶
  1. 一、基础结构对比
    1. 数据结构定义
      1. Java HashMap
      2. Redis字典
    2. 主要区别与设计思路
  2. 二、关键操作API对比
    1. 初始化
      1. Java HashMap
      2. Redis字典
    2. 添加元素
      1. Java HashMap
      2. Redis字典
    3. 查找元素
      1. Java HashMap
      2. Redis字典
    4. 删除元素
      1. Java HashMap
      2. Redis字典
    5. 扩容/重哈希操作
      1. Java HashMap
      2. Redis字典
  3. 三、性能设计考量
    1. 哈希函数设计
      1. Java HashMap
      2. Redis字典
    2. 冲突处理
      1. Java HashMap
      2. Redis字典
    3. 迭代器设计
      1. Java HashMap
      2. Redis字典
  4. 四、内存管理与性能权衡
    1. 内存布局
      1. Java HashMap
      2. Redis字典
    2. 时间-空间权衡
      1. Java HashMap
      2. Redis字典
  5. 五、线程安全考虑
    1. Java HashMap
    2. Redis字典
  6. 六、特殊功能比较
    1. 随机访问
      1. Java HashMap
      2. Redis字典
    2. 批量操作
      1. Java HashMap
      2. Redis字典
  7. 七、哈希冲突处理机制详解
    1. Java HashMap的树化机制
    2. Redis的渐进式rehash机制
  8. 八、总结与实践建议
    1. 设计决策对比
    2. 适用场景建议
      1. Java HashMap适合：
      2. Redis 字典适合：
    3. 设计启示
  9. 九、源码深入剖析
    1. 哈希函数的设计哲学
      1. Java HashMap的位扩散设计
      2. Redis多种哈希函数
    2. 扩容和缩容的精细控制
      1. Java HashMap的扩容策略
      2. Redis的扩缩容控制
    3. 内存布局和缓存效率
      1. Java HashMap的内存特性
      2. Redis字典的内存特性
  10. 十、实际应用场景示例
    1. 场景1：高频读取、低频写入
      1. Java HashMap的表现
    2. 场景2：实时交易系统
      1. Redis字典的表现
    3. 场景3：内存优化
      1. Java HashMap的表现
      2. Redis字典的表现
  11. 结论