资讯专栏INFORMATION COLUMN

HashMap实现思路(小白科普)

Joyven / 2603人阅读

摘要:数据结构小白科普是和中常用的一个容器,采用了数组链表的结构来存储数据新增红黑树,当链表长度大于以后,链表会进化成红黑树。下面具体分析的实现思路。

Android 数据结构 java 小白科普

HashMap是java和Android中常用的一个容器,采用了数组+链表的结构来存储数据(PS:jdk1.8新增红黑树,当链表长度大于8以后,链表会进化成红黑树)。下面具体分析HashMap的实现思路。

1 为什么要用链表

很多人疑惑,实现HashMap直接用数组不就可以了吗,通过hash函数计算出key对应的数组的下标,value直接存进去。为什么会用链表呢?
问题的关键就出在hash函数身上,因为到现在为止还没有出现一种一个不同的key对应的hash值都不一样的函数,(包括MD5,SHA等算法),假如a,b两个key通过hash函数得到的数组下标都是1,a已经存进数组下标为1的位置,b该怎么存储呢?把a对应的value删了,替换成b对应的value?这种作法显然是不可取的。所以在HashMap中引入了链表,还是a,b两个key,存储a的时候,我们先判断下数组下标为1的位置是否有数据,如果没有直接插入数组中,这时候a对应的value插入到了数组中,这时候我们来存储b,我们发现下标为1的位置已经存了数据,我们用a.next来指向b,形成一个链表。以此类推。

2 代码实现 1 put方法
 public V put(K key, V value) {
        //hash()散列函数,主要作用通过一系列计算,得出应存在数组的下标
        return putVal(hash(key), key, value, false, true);
 }
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
        //扩容数据搬迁
            n = (tab = resize()).length;
        //查看对应下标是否有数据,没有数据直接插入数据
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
             //进化成红黑树之后
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    //判断是不是链表最后一个节点
                    if ((e = p.next) == null) {
                        //发现是最后一个节点的话,添加在队尾
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //key相等
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //重新赋值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
2 get方法
 public V get(Object key) {
        Node e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {//取出数组中对应下标数据
            //key相同 hash相同 数组中的对象就是我们要找的
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {
                //循环遍历 找到key相同的对象
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
}
3 总结

HashMap通过数组加链表的方式,实现了时间复杂度为O(1)的快速插入,查询等操作,在平时使用中我们还可以通过指定数组大小来进一步加快它的性能。
文章中只是写了大概的思路,有不对的还请见谅!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/72544.html

相关文章

  • 郑方方打怪升级日记 — 初识HTML5与CSS3

    摘要:任务名称响应式砸蛋页面任务背景前辈方方啊最近项目也没什么事情你看这个砸蛋页面不是很好看要不你做一个响应式砸蛋页面吧系统郑方方接下前辈的任务郑方方自动解析任务步骤任务响应式砸蛋页面与入门阅读秘籍响应式布局制作层搭配搭配控制器完成任务人物背 任务名称:响应式砸蛋页面 任务背景 前辈:方方啊,最近项目也没什么事情,你看这个砸蛋页面不是很好看,要不你做一个响应式砸蛋页面吧? 系统:郑方方接下前...

    spademan 评论0 收藏0
  • 郑方方打怪升级日记 — 初识HTML5与CSS3

    摘要:任务名称响应式砸蛋页面任务背景前辈方方啊最近项目也没什么事情你看这个砸蛋页面不是很好看要不你做一个响应式砸蛋页面吧系统郑方方接下前辈的任务郑方方自动解析任务步骤任务响应式砸蛋页面与入门阅读秘籍响应式布局制作层搭配搭配控制器完成任务人物背 任务名称:响应式砸蛋页面 任务背景 前辈:方方啊,最近项目也没什么事情,你看这个砸蛋页面不是很好看,要不你做一个响应式砸蛋页面吧? 系统:郑方方接下前...

    justCoding 评论0 收藏0
  • 郑方方打怪升级日记 — 初识HTML5与CSS3

    摘要:任务名称响应式砸蛋页面任务背景前辈方方啊最近项目也没什么事情你看这个砸蛋页面不是很好看要不你做一个响应式砸蛋页面吧系统郑方方接下前辈的任务郑方方自动解析任务步骤任务响应式砸蛋页面与入门阅读秘籍响应式布局制作层搭配搭配控制器完成任务人物背 任务名称:响应式砸蛋页面 任务背景 前辈:方方啊,最近项目也没什么事情,你看这个砸蛋页面不是很好看,要不你做一个响应式砸蛋页面吧? 系统:郑方方接下前...

    jemygraw 评论0 收藏0

发表评论

0条评论

Joyven

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<