java基础：使用拉链法解决hash冲突代码示例

拼搏现实的明天。 2024-02-20 11:50 56阅读 0赞

拉链法（Chaining）是一种常见的解决哈希冲突的方法之一。它通过在哈希表中的每个槽中使用一个链表或其他数据结构来存储具有相同哈希码的元素。当发生哈希冲突时，新元素将添加到链表的末尾。

以下是拉链法解决哈希冲突的基本步骤：

1.  创建一个哈希表，其中包含一定数量的槽（桶）。
2.  当插入一个新元素时，计算其哈希码。
3.  根据哈希码确定要插入的槽位置。
4.  如果该槽为空，将新元素插入该位置。
5.  如果该槽已经有元素存在，遍历链表或其他数据结构，直到找到链表的末尾。
6.  在链表末尾添加新元素。
7.  当需要查找、删除或更新元素时，使用相同的哈希码来定位元素所在的槽，然后在链表中执行相应的操作。

下面是一个简单的示例，演示了使用拉链法解决哈希冲突的过程：

import java.util.LinkedList;
    
    public class ChainingHashTable {
        
        private LinkedList<Entry>[] table;
        private int capacity;
    
        public ChainingHashTable(int capacity) {
        
            this.capacity = capacity;
            table = new LinkedList[capacity];
            for (int i = 0; i < capacity; i++) {
        
                table[i] = new LinkedList<>();
            }
        }
    
        public void put(int key, String value) {
        
            int index = hash(key);
            LinkedList<Entry> list = table[index];
            for (Entry entry : list) {
        
                if (entry.key == key) {
        
                    entry.value = value;
                    return;
                }
            }
            list.add(new Entry(key, value));
        }
    
        public String get(int key) {
        
            int index = hash(key);
            LinkedList<Entry> list = table[index];
            for (Entry entry : list) {
        
                if (entry.key == key) {
        
                    return entry.value;
                }
            }
            return null;
        }
    
        private int hash(int key) {
        
            return key % capacity;
        }
    
        private static class Entry {
        
            private int key;
            private String value;
    
            public Entry(int key, String value) {
        
                this.key = key;
                this.value = value;
            }
        }
    
        public static void main(String[] args) {
        
            ChainingHashTable hashTable = new ChainingHashTable(10);
            hashTable.put(1, "Value 1");
            hashTable.put(11, "Value 11");
            hashTable.put(21, "Value 21");
    
            System.out.println(hashTable.get(1));   // Output: Value 1
            System.out.println(hashTable.get(11));  // Output: Value 11
            System.out.println(hashTable.get(21));  // Output: Value 21
        }
    }

在上面的示例中，我们创建了一个简单的哈希表 `ChainingHashTable`，使用链表作为冲突解决方法。在 `put()` 方法中，我们计算键的哈希码并找到对应的槽，然后遍历链表以检查是否已经存在具有相同键的元素。如果存在，我们更新其值；否则，我们将新的键值对添加到链表的末尾。在 `get()` 方法中，我们根据键的哈希码找到对应的槽，然后遍历链表以查找具有相同键的元素并返回其值。

拉链法是一种常见且有效的解决哈希冲突的方法，它允许在哈希表中存储具有相同哈希码的多个元素，并提供了高效的插入、查找和删除操作。