哈希冲突与解决策略（拉链寻址、开放寻址等）

哈希冲突：当不同的键通过哈希函数映射到相同的索引位置时，就发生了哈希冲突。

解决策略：

        拉链法（Chaining）：每个哈希桶（数组位置）不直接存储元素，而是存储一个链表的头节点。所有哈希值相同的元素都放在这个链表中。优点：实现简单、删除操作容易、元素数量不受数组大小限制、负载因子可以大于1 。缺点：需要额外的指针空间、缓存不友好（链表节点在内存中不连续）

        拉链法示意图：

// 哈希表数组
索引:  0     1     2     3     4     5     6     7
      ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓
     null  null  null  null  null  null  null  null

// 插入元素后
索引0: [ (A,10) ] → [ (B,20) ] → null    (两个元素hash值都是0)
索引1: null
索引2: [ (C,30) ] → null
索引3: [ (D,40) ] → [ (E,50) ] → [ (F,60) ] → null
索引4: null
...

        开放寻址（Open Addressing）：当发生冲突时，不是创建链表，而是通过探查方式（如线性探查、二次探查等）在数组中寻找下一个空位置存放元素。所有元素都直接存储在数组中。

        线性探查：

// 当位置 i 被占用时，依次尝试 i+1, i+2, i+3, ...
// 公式：hash(key) + 1, +2, +3 ...

// 示例：插入 key=17，hash=1
初始数组：
[null, null, null, null, null, null, null, null]

1. 插入 A(1) → 索引1
[null, A, null, null, null, null, null, null]

2. 插入 B(17) → hash=1 被占，尝试2 → 空，放入
[null, A, B, null, null, null, null, null]

3. 插入 C(33) → hash=1 被占，尝试2被占，尝试3 → 空，放入
[null, A, B, C, null, null, null, null]

4. 查找 B(17)：从1开始，找到2，key匹配，返回

        二次探查：

// 当位置 i 被占用时，依次尝试 i+1², i+2², i+3², ...
// 公式：hash(key) + 1², +2², +3² ...

// 示例
hash = 3，被占：
尝试 3 + 1² = 4
尝试 3 + 2² = 7
尝试 3 + 3² = 12
...

实现简单HashMap

实现原理：使用哈希表存储键值对。哈希函数将键映射到数组的索引位置，处理冲突时可以选择拉链法或开放寻址法。

哈希表操作：

        插入：计算键的哈希值，将元素插入到对应位置。

        查找：根据键的哈希值查找对应的值。

        删除：根据键的哈希值删除对应的键值对。

示例:

import java.util.Objects;

public class simpleHashMap<K,V> {
    static class Node<K, V> {
        final K key;      // 键
        V value;          // 值
        Node<K, V> next;  // 下一个节点（处理哈希冲突）
        Node(K key,V value){
            this.key = key;
            this.value = value;
            this.next = null;
        }
        // 所有类都继承自 Object, Object 类的默认 toString(),所以需要重写方法
        @Override
        public String toString() {
            return key + "=" + value;
        }
    }
    private Node<K, V>[] table;      // 数组（桶）
    private int size;                 // 元素个数
    private static final int DEFAULT_CAPACITY = 16;  // 默认容量
    private static final float LOAD_FACTOR = 0.75f;   // 负载因子
    @SuppressWarnings("unchecked")
    public simpleHashMap(){
        table = (Node<K,V>[]) new Node[DEFAULT_CAPACITY];
        size = 0;
    }
    private int hash(K key){     //取模法哈希函数
        if(key == null)
            return 0;
        int h = key.hashCode(); //hashCode()是生成一个原始的数字
        return Math.abs(h)%table.length;
    }
    public V put(K key,V value){
        int index = hash(key);
        Node<K,V> head = table[index];
        Node<K,V> current = head;
        while(current!=null){
            if(Objects.equals(current.key,key)){
                V oldValue = current.value;
                current.value = value;
                return oldValue;
            }
            current = current.next;
        }
        // key 不存在，创建新节点，插入链表头部
        Node<K,V> newNode = new Node<>(key,value);
        newNode.next = head;
        table[index] = newNode;
        size++;
        if(size>table.length*LOAD_FACTOR){
            resize();
        }
        return null;
    }
    // get 方法
    public V get(K key){
        int index = hash(key);
        Node<K,V> current = table[index];
        while(current!=null){
            if(Objects.equals(current.key,key)){
                return current.value;
            }
            current = current.next;
        }
        return null;
    }
    // remove 方法：删除键值对
    public V remove(K key) {
        int index = hash(key);
        Node<K,V> current = table[index];
        Node<K,V> prev = null;
        while(current!=null){
            if(Objects.equals(current.key,key)){
                if(prev == null){
                    table[index] = current.next;
                }
                else{
                    prev.next = current.next;
                }
            }
            prev = current;
            current = current.next;
        }
        return null;
    }
    @SuppressWarnings("unchecked")
    public void resize(){
        int oldCapacity = table.length;
        int newCapacity = oldCapacity*2;
        Node<K,V>[] newTable = (Node<K,V>[]) new Node[newCapacity];
        for(int i=0;i<oldCapacity;i++){
            Node<K,V> current = table[i];
            while(current!=null){
                Node<K,V> next = current.next;
                int newIndex = Math.abs(current.key.hashCode())%newCapacity;
                current.next = newTable[newIndex];
                newTable[newIndex] = current;
                current=next;
            }
        }
        table = newTable;
    }
}

设计哈希函数

目的：设计一个好的哈希函数，确保哈希值均匀分布，避免大量哈希冲突。

常用方法：

        取模法：将键的哈希值对哈希表的大小取模。

    // 简单的取模哈希
    public static int modHash(int key, int tableSize) {
        return key % tableSize;
    }
    
    // 处理负数的取模
    public static int modHashSafe(int key, int tableSize) {
        return Math.abs(key) % tableSize;
    }
    
    // 位运算取模（当 tableSize 是 2 的幂时）
    public static int modHashBit(int key, int tableSize) {
        // tableSize 必须是 2 的幂，如 16, 32, 64...
        return key & (tableSize - 1);  // 位运算，更快
    }

        字符串哈希：对于字符串，可以逐个字符进行哈希，然后结合前一个字符的哈希值。

    // 1. 简单累加法（容易冲突）
    public static int simpleStringHash(String str, int tableSize) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash += str.charAt(i);  // 简单累加字符的 ASCII 值
        }
        return Math.abs(hash) % tableSize;
    }
    
    // 2. 多项式哈希（Java String 的 hashCode 方法）
    public static int polynomialHash(String str) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            // s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
            hash = 31 * hash + str.charAt(i);
        }
        return hash;
    }
    
    // 3. 带取模的多项式哈希
    public static int polynomialHashWithMod(String str, int tableSize) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = (31 * hash + str.charAt(i)) % tableSize;
        }
        return Math.abs(hash) % tableSize;
    }
    
    // 4. BKDR 哈希算法（常用）
    public static int bkdrHash(String str, int tableSize) {
        int hash = 0;
        int seed = 131;  // 31 131 1313 13131 131313 等质数
        
        for (int i = 0; i < str.length(); i++) {
            hash = hash * seed + str.charAt(i);
        }
        
        return Math.abs(hash) % tableSize;
    }
    
    // 5. DJB2 哈希算法
    public static int djb2Hash(String str, int tableSize) {
        int hash = 5381;
        
        for (int i = 0; i < str.length(); i++) {
            hash = ((hash << 5) + hash) + str.charAt(i);  // hash * 33 + c
        }
        
        return Math.abs(hash) % tableSize;
    }
    
    // 6. SDBM 哈希算法
    public static int sdbmHash(String str, int tableSize) {
        int hash = 0;
        
        for (int i = 0; i < str.length(); i++) {
            hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
        }
        
        return Math.abs(hash) % tableSize;
    }

# 散列表 # 哈希算法 # 数据结构
Logo
乐奇 Rokid 开放社区

更多推荐

cover

AR 技术科普：光波导是什么，为什么警务要用它

avatar 乐奇 Rokid 开放社区
cover

LVGL嵌入式UI开发教程：AIUI Studio可视化编辑器实操指南

avatar 乐奇 Rokid 开放社区
cover

影目Air3被召回，智能眼镜迎来散热大考

avatar 乐奇 Rokid 开放社区