|
哈希表，是所有高级语言都有的一种数据结构，只是叫法可能不同，有些叫做字典(dict)，有些叫哈希(hash)，有些叫映射(map)，其实说的都是同一种东西。阅读源代码可以深入细节，让我们来看看Java C# Lua Redis这些编程语言或者应用对于哈希表的实现有哪些异同点。先来看一张总结的表格:
| 实现 | 版本 | 数据结构/类 | 哈希冲突解决方式 | 装载因子 | rehash扩容 |
|---|
| Java | 8 | Hashtable | 拉链法 | 0.75 | 阻塞，分配两倍内存 | | Java | 8 | Hashmap | 拉链法 | 0.75 | 阻塞，分配两倍内存 | | C# | .net core 3.1 | Hashtable | 开地址法 | 0.72 | 阻塞，分配特定内存 | | C# | .net core 3.1 | Dictionary | 开地址法 | 1.0 | 阻塞，分配特定内存 | | Lua | 5.3 | table | 开地址法 | 无 | 阻塞，分配两倍内存 | | Go | 1.14 | map | 拉链法 | 6.5 or overflow | 渐进式非阻塞，分配两倍内存 | | Redis | 2.8.24 | dict | 拉链法 | 1.0 or 5.0 | 渐进式非阻塞，分配两倍内存 |
拉链法: Separate chaining
开地址法: Open addressing
哈希冲突: hash collision
Java，C#和Redis都是通过检测装载因子触发rehash，Lua中为什么没有最佳装载因子去触发rehash，它又是怎么触发rehash的？
Java，C#和Redis的最佳装载因子为什么不同？
Java与Redis都使用了拉链法解决哈希冲突？它们在实现上有什么区别？
C#和Lua都使用了开地址法解决哈希冲突？它们在实现上有什么区别？
为何C# 在rehash时，需要分配特定数量内存，而不是两倍？
|