[Java] Hashmap的内部实现

来源:网页教学基地 时间:2017-01-11 09:01:28  浏览次数:0


原始数据结构

    在记录Hashmap的内部实现之前 先复习下 学校里面学过的一下基本数据结构吧。

    数组

        在简单不过了,在课堂学习的时候,学的最多的就是 数组的寻址和插入了,和java 中的数组没两样,从空间和时间的计算角度看,数组是一个空间优于时间的一种数据结构

    链表

        在学完数组之后,老师一定介绍过可以快速插入的数据结构那就是链表啦,每个节点用 Next的来做链接啦。

    二叉树

        在学完链表之后,老师又教了一种看似高端的数据结构, 那就是二叉树啦,也就是所谓的红黑树,它的优势在于节点数量达到一定级别后检束数度要大于链表。

Hash表

HashMap基于Hash算法,我们通过put(key,value)存储,get(key)来获取。当传入key时,HashMap会根据 key.hashCode()计算出hash值,根据hash值将value保存在bucket里。当计算出的hash值相同时怎么办呢,我们称之为 Hash冲突,HashMap的做法是用链表和红黑树存储相同hash值的value。当Hash冲突的个数比较少时,使用链表,否则使用红黑树。



------------------TBD----------------------


最近相关