用拉链法实现哈希表

您所在的位置：网站首页 › 隐形拉链头的上法图解 › 用拉链法实现哈希表

用拉链法实现哈希表

2024-06-13 13:39| 来源: 网络整理| 查看: 265

前文哈希表核心原理中我介绍了哈希表的核心原理和几个关键概念，其中提到了解决哈希冲突的方法主要有两种，分别是拉链法和开放寻址法（也常叫做线性探查法）：

本文就来具体介绍一下拉链法的实现原理和代码。

首先，我会结合可视化面板用拉链法实现一个简化版的哈希表，带大家直观地理解拉链法是如何实现增删查改的 API 并解决哈希冲突的，最后再给出一个比较完善的 Java 代码实现。

拉链法的简化版实现

哈希表核心原理已经介绍过哈希函数和 key 的类型的关系，其中 hash 函数的作用是在 O(1) 的时间把 key 转化成数组的索引，而 key 可以是任意不可变的类型。

但是这里为了方便诸位理解，我先做如下简化：

1、我们实现的哈希表只支持 key 类型为 int，value 类型为 int 的情况，如果 key 不存在，就返回 -1。

2、我们实现的 hash 函数就是简单地取模，即 hash(key) = key % table.length。这样也方便模拟出哈希冲突的情况，比如当 table.length = 10 时，hash(1) 和 hash(11) 的值都是 1。

3、底层的 table 数组的大小在创建哈希表时就固定，不考虑负载因子和动态扩缩容的问题。

这些简化能够帮助我们聚焦增删查改的核心逻辑，并且可以借助可视化面板辅助大家学习理解。

简化版代码

这里直接给出简化版的代码实现，你可以先看看，后面将通过可视化面板展示增删查改的过程：

java 🟢import java.util.LinkedList; // 用拉链法解决哈希冲突的简化实现 public class ExampleChainingHashMap { // 链表节点，存储 key-value 对儿 // 注意这里必须存储同时存储 key 和 value // 因为要通过 key 找到对应的 value static class KVNode { int key; int value; // 为了简化，我这里直接用标准库的 LinkedList 链表 // 所以这里就不添加 next 指针了 // 你当然可以给 KVNode 添加 next 指针，自己实现链表操作 public KVNode(int key, int value) { this.key = key; this.value = value; } } // 底层 table 数组中的每个元素是一个链表 private LinkedList[] table; public ExampleChainingHashMap(int capacity) { table = new LinkedList[capacity]; } private int hash(int key) { return key % table.length; } // 查 public int get(int key) { int index = hash(key); if (table[index] == null) { // 链表为空，说明 key 不存在 return -1; } LinkedList list = table[index]; // 遍历链表，尝试查找目标 key，返回对应的 value for (KVNode node : list) { if (node.key == key) { return node.value; } } // 链表中没有目标 key return -1; } // 增/改 public void put(int key, int value) { int index = hash(key); if (table[index] == null) { // 链表为空，新建一个链表，插入 key-value table[index] = new LinkedList(); table[index].add(new KVNode(key, value)); return; } // 链表不为空，要遍历一遍看看 key 是否已经存在 // 如果存在，更新 value // 如果不存在，插入新节点 LinkedList list = table[index]; for (KVNode node : list) { if (node.key == key) { // key 已经存在，更新 value node.value = value; return; } } // 链表中没有目标 key，添加新节点 // 这里使用 addFirst 添加到链表头部或者 addLast 添加到链表尾部都可以 // 因为 Java LinkedList 的底层实现是双链表，头尾操作都是 O(1) 的 // https://labuladong.online/algo/data-structure-basic/linkedlist-implement/ list.addLast(new KVNode(key, value)); } // 删 public void remove(int key) { LinkedList list = table[hash(key)]; if (list == null) { return; } // 如果 key 存在，则删除 // 这个 removeIf 方法是 Java LinkedList 的方法，可以删除满足条件的元素，时间复杂度 O(N) list.removeIf(node -> node.key == key); } } cpp 🤖// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。 // 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。 #include #include #include // 用拉链法解决哈希冲突的简化实现 class ExampleChainingHashMap { // 链表节点，存储 key-value 对儿 // 注意这里必须存储同时存储 key 和 value // 因为要通过 key 找到对应的 value struct KVNode { int key; int value; // 为了简化，我这里直接用标准库的 LinkedList 链表 // 所以这里就不添加 next 指针了 // 你当然可以给 KVNode 添加 next 指针，自己实现链表操作 KVNode(int key, int value) : key(key), value(value) {} }; // 底层 table 数组中的每个元素是一个链表 std::vector table; public: ExampleChainingHashMap(int capacity) : table(capacity) {} int hash(int key) { return key % table.size(); } // 查 int get(int key) { int index = hash(key); if (table[index].empty()) { // 链表为空，说明 key 不存在 return -1; } for (const auto& node : table[index]) { if (node.key == key) { return node.value; } } // 链表中没有目标 key return -1; } // 增/改 void put(int key, int value) { int index = hash(key); if (table[index].empty()) { // 链表为空，新建一个链表，插入 key-value table[index].push_back(KVNode(key, value)); return; } // 链表不为空，要遍历一遍看看 key 是否已经存在 // 如果存在，更新 value // 如果不存在，插入新节点 for (auto& node : table[index]) { if (node.key == key) { // key 已经存在，更新 value node.value = value; return; } } // 链表中没有目标 key，添加新节点 // 这里使用 addFirst 添加到链表头部或者 addLast 添加到链表尾部都可以 // 因为 Java LinkedList 的底层实现是双链表，头尾操作都是 O(1) 的 // https://labuladong.online/algo/data-structure-basic/linkedlist-implement/ table[index].push_back(KVNode(key, value)); } // 删 void remove(int key) { auto& list = table[hash(key)]; if (list.empty()) { return; } // 如果 key 存在，则删除 // 这个 removeIf 方法是 Java LinkedList 的方法，可以删除满足条件的元素，时间复杂度 O(N) list.remove_if([key](KVNode& node) { return node.key == key; }); } }; python 🤖# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。 # 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。 class KVNode: # 链表节点，存储 key-value 对儿 def __init__(self, key, value): self.key = key self.value = value class ExampleChainingHashMap: def __init__(self, capacity): # 底层 table 数组中的每个元素是一个链表 self.table = [None] * capacity def hash(self, key): return key % len(self.table) def get(self, key): # 查 index = self.hash(key) if self.table[index] is None: # 链表为空，说明 key 不存在 return -1 list = self.table[index] # 遍历链表，尝试查找目标 key，返回对应的 value for node in list: if node.key == key: return node.value # 链表中没有目标 key return -1 def put(self, key, value): # 增/改 index = self.hash(key) if self.table[index] is None: # 链表为空，新建一个链表，插入 key-value self.table[index] = [] self.table[index].append(KVNode(key, value)) return list = self.table[index] for node in list: if node.key == key: # key 已经存在，更新 value node.value = value return # 链表中没有目标 key，添加新节点 list.append(KVNode(key, value)) def remove(self, key): # 删 list = self.table[self.hash(key)] if list is None: return # 如果 key 存在，则删除 list[:] = [node for node in list if node.key != key] go 🤖// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。 // 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。 import "container/list" // 用拉链法解决哈希冲突的简化实现 type KVNode struct { key int value int } // 底层 table 数组中的每个元素是一个链表 type ExampleChainingHashMap struct { table []*list.List } // 注意这里必须存储同时存储 key 和 value // 因为要通过 key 找到对应的 value func NewExampleChainingHashMap(capacity int) ExampleChainingHashMap { return ExampleChainingHashMap{ table: make([]*list.List, capacity), } } func (h *ExampleChainingHashMap) hash(key int) int { return key % len(h.table) } // 查 func (h *ExampleChainingHashMap) Get(key int) (int, bool) { index := h.hash(key) if h.table[index] == nil { // 链表为空，说明 key 不存在 return -1, false } for e := h.table[index].Front(); e != nil; e = e.Next() { node := e.Value.(KVNode) if node.key == key { return node.value, true } } // 链表中没有目标 key return -1, false } // 增/改 func (h *ExampleChainingHashMap) Put(key int, value int) { index := h.hash(key) if h.table[index] == nil { // 链表为空，新建一个链表，插入 key-value h.table[index] = list.New() h.table[index].PushBack(KVNode{key, value}) return } for e := h.table[index].Front(); e != nil; e = e.Next() { node := e.Value.(KVNode) if node.key == key { // key 已经存在，更新 value node.value = value return } } // 链表中没有目标 key，添加新节点 // 这里使用 addFirst 添加到链表头部或者 addLast 添加到链表尾部都可以 // 因为 Java LinkedList 的底层实现是双链表，头尾操作都是 O(1) 的 h.table[index].PushBack(KVNode{key, value}) } // 删 func (h *ExampleChainingHashMap) Remove(key int) { index := h.hash(key) if h.table[index] == nil { return } for e := h.table[index].Front(); e != nil; e = e.Next() { node := e.Value.(KVNode) if node.key == key { // 如果 key 存在，则删除 h.table[index].Remove(e) return } } } javascript 🤖// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。 // 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。 // 用拉链法解决哈希冲突的简化实现 var ExampleChainingHashMap = function(capacity) { // 链表节点，存储 key-value 对儿 // 注意这里必须存储同时存储 key 和 value // 因为要通过 key 找到对应的 value var KVNode = function(key, value) { this.key = key; this.value = value; }; // 底层 table 数组中的每个元素是一个链表 this.table = new Array(capacity); this.hash = function(key) { return key % this.table.length; }; // 查 this.get = function(key) { var index = this.hash(key); if (this.table[index] == null) { // 链表为空，说明 key 不存在 return -1; } var list = this.table[index]; // 遍历链表，尝试查找目标 key，返回对应的 value for (var i = 0; i

【本文地址】

用拉链法实现哈希表

用拉链法实现哈希表

今日新闻

推荐新闻