多线程情况下实时扩展hash map

Question

这个可能不一定是针对java的hash map实现，因为java的hash map可以用synchronizedMap()来获得线程安全的hash map。但是我目前使用的hash table非常大，如果每次发生冲突进行extend操作时对全表加锁，会消耗很多时间，我希望可以在extend的同时仍然可以同步进行一些非互斥的读写操作。例如4个bucket的hashmap，采用h1(x)=x mod 4，当扩展时将变为h2(x)= x mod 8，那么原本存储在0，1，2，3号bucket中的元素需要redistribute，但是在进行redistribute的过程中如果有读或写的访问，就可能出现不一致。例如 x=6，原来在2号bucket，当我们扩展后h2(x)指向6号bucket，但是实际的值可能还没有被copy到相应的bucket里。所以需要设计一个机制来决定相应的hash function。Thanks。

Answer 1

使用那个       java.util.concurrent.ConcurrentHashMap<K,V>

Answer 2

JAVA 本身有提供这个的东西

Answer 3

ConcurrentHashMap 采用分离锁，默认情况下拥有 16 把锁，是部分加锁的，如果两个线程操作不同的 key 可能就用不同的锁，这样就能并发了。ConcurrentHashMap 在多线程下性能比 Hashtable, 同步 HashMap 高出很多。也就是说在 JDK 5 或者之后的版本实在没有理由再去使用 Hashtable、同步的 HashMap 了。