具有单独链接冲突解决方案的Java哈希表? [英] Java hashtable with separate chaining collision resolution?
问题描述
我使用内置的java.util.hashtable创建了一个程序,但现在我需要使用单独的链接来解决冲突。是否可以使用哈希表的这种实现?是否有一个已实现使用单独链接?
I have created a program using the built in java.util.hashtable but now I need to resolve collisions using separate chaining. Is it possible with this implementation of a hashtable? Is there one out there already implemented that uses separate chaining?
推荐答案
查看源,看起来它已经使用了单独的链接。如果您从第901行开始查看条目< K,V>
类,您会看到它引用另一个名为的条目
。然后,如果您查看 put()
方法,则在第420行上, next
引用将通过构造函数填充为以前存储在该存储桶中的任何元素。
Looking at the source of the Hashtable implementation, it looks like it already uses separate chaining. If you look at the Entry<K,V>
class starting at line 901, you'll see that it has a reference to another Entry named next
. If you then look at the put()
method, on line 420 the next
reference is populated via the constructor to be whatever element was previously stored in that bucket.
请注意,您通常不应该关注这些实现细节。 Java Collections Framework可能是Java中使用最广泛的框架之一,因此您应该假设作者已经将性能调整到最佳状态。
Note that you shouldn't generally be concerned about implementation details such as these. The Java Collections Framework is probably one of the most widely used frameworks in Java, and as such you should assume that the authors have tuned the performance to be as good as it's going to get.
我想指出的另一件事是Hashtable类主要被 HashMap
class(也使用单独的链接,参见这里)。两者之间的主要区别是 Hashtable
中的所有方法都是同步的,而在 HashMap
中则不是。这可以在您在单线程环境中运行的情况下获得更好的性能(可能是这个问题的原因?)。
One other thing I'd like to point out is that the Hashtable class has been mostly replaced by the HashMap
class (which also uses separate chaining, see here). The main difference between the two is that all of the methods in Hashtable
are synchronized, whereas in HashMap
they are not. This leads to better performance in situations where you are running in a single threaded environment (possibly the reason for this question?).
如果你做需要线程安全的地图实现,那么你应该考虑在调用 HashMap javase / 6 / docs / api / java / util / Collections.html#synchronizedMap(java.util.Map)rel =nofollow noreferrer> Collections.synchronizedMap()
,或使用 ConcurrentHashMap
。
If you do need a thread-safe map implementation, then you should consider either wrapping a normal HashMap
in a call to Collections.synchronizedMap()
, or using a ConcurrentHashMap
.
这篇关于具有单独链接冲突解决方案的Java哈希表?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!