HashMap底层实现原理,以及和Hashtable的比较
HashMap底层实现原理,以及和Hashtable的比较
懿宁19931210 发表于1个月前
HashMap底层实现原理,以及和Hashtable的比较
  • 发表于 1个月前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

我们要知道HashMap底层实现是数组(Entry类型)加上链表的数据结构---拉链法实现哈希表Entry 实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数。

1.通过hash()函数,计算key对应的哈希值,找到数组中存储位置,在冲突(不同的关键字,对应相同的哈希值,在)较少的情况下,他的查询效率是很高的,如果发生冲突就在数组元素所在链表的表头插入该值,所以在查找HashMap时候有两个关键函数,一个是hash()函数找到key在数组中的位置,一个是equals()函数,在链表中找到key,返回value,通常返回某关键字时候用的判断方法:(key==null ? k==null :key.equlas(k)),可见关键字可以为null

   2.Hashtable 的实例有两个参数影响其性能:初始容量 和 加载因子。容量是哈希表中桶的数量,初始容量 就是哈希表创建时的容量。注意,哈希表的状态为 open:在发生“哈希冲突”的情况下,单个桶会存储多个条目,这些条目必须按顺序搜索。加载因子是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 rehash 方法的具体细节则依赖于该实现。通常,默认加载因子是 0.75(当数据元素个数达到数组总容量的75%时候,要对数组进行动态扩展), 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查找某个条目的时间(在大多数 Hashtable 操作中,包括 get 和 put 操作,都反映了这一点)。

共有 人打赏支持
粉丝 0
博文 25
码字总数 7078
×
懿宁19931210
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: