ST.*_*ST. 2 java hashtable hashmap hashcode data-structures
我知道的哈希结构 - HashTable,HashSet和HashMap.
难道他们都使用桶结构-即当两个散列码是类似 一模一样的一个元素不会覆盖其他的,相反,它们被放置在与哈希码相关联的同一个桶？
在Sun目前的Java库IdentityHashMap实现中,以及ThreadLocal使用探测结构的内部实现.
在Java中探测哈希表的一般问题是,hashCode并且equals可能相对昂贵.因此,您希望缓存哈希值.你不能有一个混合引用和基元的数组,所以你需要做一些相对复杂的事情.另一方面,如果您使用==检查匹配,那么您可以检查许多引用而不会出现性能问题.
IIRC,Azul有一个快速并发的二次探测哈希映射.
一个链表在每个桶用于处理哈希冲突.请注意,java HashSet实际上是由HashMap底层实现的(所有键都映射到所有HashSets 上的相同单例值),因此使用相同的桶结构.
如果添加了一个元素,则会在链接列表(via .equals)中的所有项目之前检查其相等性,然后再添加它.因此,具有散列冲突特别糟糕,因为当链表变大时,这可能是昂贵的检查.
我相信Java哈希结构在执行散列时都使用一种链接形式来处理colisions - 它将具有相同散列的项放入列表中.
我不相信Java使用开放式寻址来获得基于散列的数据结构(开放式寻址重新计算基于重试序列的散列,直到它在表中找到一个开放的切口)
| 归档时间： |
|
| 查看次数： |
2648 次 |
| 最近记录： |