哈希表笔记（四）Redis对比Java总结

一、基础结构对比

数据结构定义

Java HashMap

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字典

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

// 默认构造函数
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字典

// 创建字典
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

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字典

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

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字典

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

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字典

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

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字典

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

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提供多种哈希函数：

// 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检测并发修改

// 并发修改检测
if (modCount != expectedModCount)
    throw new ConcurrentModificationException();

Redis字典

• 单线程模型：Redis主要是单线程架构，字典操作天然线程安全
• RDB持久化保护：在fork子进程时可禁用rehash

// 可控制的rehash开关
void dictDisableResize(void) {
    dict_can_resize = 0;
}

void dictEnableResize(void) {
    dict_can_resize = 1;
}

• 指纹机制：使用dictFingerprint()检测字典的非法修改

设计理念对比：

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

六、特殊功能比较

随机访问

Java HashMap

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

Redis字典

// 随机返回一个键值对
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

// 批量添加
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的树化机制

// 树化阈值
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机制

// 执行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适合：

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的位扩散设计

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的扩容策略

// 当前大小翻倍
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的扩缩容控制

// 扩容检查
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的表现

// 初始化足够大的容量以避免扩容
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字典的表现

// 在处理交易期间临时禁用rehash
dictDisableResize();

// 交易处理
processTransaction();

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

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

场景3：内存优化

Java HashMap的表现

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

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

Redis字典的表现

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

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

结论

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

• Java HashMap 更注重通用性、最坏情况保证和整体内存效率，适合作为通用集合类型
• Redis字典 更注重操作延迟的一致性、实时性和可控性，适合作为数据库核心组件