使用你熟悉的语言实现一个哈希表 HashMap，只需要支持 put 和 get 两个基本操作。 |
您所在的位置：网站首页 › 线程安全的哈希表 › 使用你熟悉的语言实现一个哈希表 HashMap，只需要支持 put 和 get 两个基本操作。 |
| 本期答案：
这道题没有一个统一的答案。哈希表常见的实现可以按照解决冲突的方式分为 Chaining 和 Open-addressing 两种。Chaining 实现将 Hash 到同一个桶的元素使用链表串联起来（也可以是其他更高效的方式），相应的，查找的时候需要查看桶中的所有元素。Open-addressing 译为开地址法，插入时一旦发现对应的桶已经被占用，则会根据某种特定方式继续寻找另一个桶，直到找到一个空的桶为止，相应地查找时也要做相同的操作。 下面给出一个 Chaining 的实现： public class MyHashTableImpl { private final Node[] buckets; public MyHashTableImpl(int expectedSize) { this.buckets = new Node[expectedSize * 4]; } public void put(K key, V value) { int h = key.hashCode() % buckets.length; Node node = new Node(key, value); node.next = buckets[h]; buckets[h] = node; } public V get(K key) { int h = key.hashCode() % buckets.length; Node node = buckets[h]; while (node != null) { if (node.key.equals(key)) { return node.value; } node = node.next; } return null; } private static class Node { final K key; final V value; Node next = null; Node(K key, V value) { this.key = key; this.value = value; } } }并发情况下，如果直接使用上述代码， buckets 上会产生数据竞争，可能导致数据结构损害。为了防止这一点，我们可以通过分段加锁来保护（类似于 JDK7 的 ConcurrentHashMap 实现）。但是，对于上面的代码来说，由于少了 rehash 的负担，我们还可以利用 CAS 实现乐观锁。这也是 JDK8+ 的 ConcurrentHashMap 使用的方案。 public class MyLockFreeHashTableImpl { private final AtomicReferenceArray buckets; public MyLockFreeHashTableImpl(int expectedSize) { this.buckets = new AtomicReferenceArray(expectedSize * 4); } public void put(K key, V value) { int h = key.hashCode() % buckets.length(); while (true) { Node node = new Node(key, value); node.next = buckets.get(h); if (buckets.compareAndSet(h, node.next, node)) { // 如果失败，则重试 return; } } } public V get(K key) { int h = key.hashCode() % buckets.length(); Node node = buckets.get(h); while (node != null) { if (node.key.equals(key)) { return node.value; } node = node.next; } return null; } static class Node { /* 略 */ } }上面的代码都是对于 Chaining 来说的，Open-addressing 也可以用类似的方式实现乐观锁，有兴趣的读者可以自己试试 ：） 最后一个问题，如果考虑 rehash，并发的实现就复杂了许多。我们依然有很多选项。最简单的一种实现，参考 JDK7 的分段加锁方案，我们可以为各个 Segment 独立加锁，这样即时某个 Segment 发生了 rehash 操作，也不会影响其他 Segment 的并发访问。多数情况下，这种实现已经能较好的满足要求。 JDK8 的 ConcurrentHashMap 实现更复杂，当需要 rehash 时，线程会逐个将 bin (bucket) 的数据复制到新的位置。此时若有其他线程并发写入时，它们也会参与到复制中来，共同协作完成哈希表的扩容。其中，每个 bin 的复制过程都通过加锁保证互斥。 而对于 Open-addressing 的哈希表，还有一些更为精妙的解决方案，有兴趣的读者可自行阅读相关论文，这里不再讨论。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |