HashMap实现原理和源码解析_Ubuntu_青云站长教程网
欢迎来到站长教程网!
  • 秒到短信接口 免费试用
  • 微信支付宝接口 秒结算
  • 中文网站排名|申请加入
  • 搜索引擎全站查询
  • 查询移动网站权重数据
  • 海外主机 台湾公司直销
  • Ubuntu

    当前位置:主页 > 服务器教程 > Ubuntu >

    HashMap实现原理和源码解析

    时间:2019-08-13|栏目:Ubuntu|点击:
  • 哈希表(hash table)也叫散列表,是一种非常重要的数据结构。许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对Java集合框架中的对应实现HashMap的实现原理进行讲解,然后会对JDK8的HashMap源码进行分析。

    一、什么是哈希表

    先了解下基本数据结构。

    数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为O(1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为O(n),对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为O(n)。

    线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为O(1),而查找操作需要遍历链表逐一进行比对,复杂度为O(n)。

    二叉树:对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

    哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1)。

    我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组存储位置 = f(关键字),f函数就是哈希函数,关键字就是key这个函数的设计好坏会直接影响到哈希表的优劣。

    HashMap实现原理和源码解析

      5.哈希冲突 : 然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

    二、HashMap实现原理

      HashMap的主干是一个Node数组。Node是HashMap的基本组成单元,每一个Node包含一个key-value键值对。

    /**
      * The table, initialized on first use, and resized as
      * necessary. When allocated, length is always a power of two.
      * (We also tolerate length zero in some operations to allow
      * bootstrapping mechanics that are currently not needed.)
      * 第一次使用的时候才进行初始化,如果有需要会重新调整大小,当重新分配内存的时候,数组长度总是2的次方
      */
      transient Node<K,V>[] table;

       Node是HashMap中的一个静态内部类。代码如下:

    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    // 与1.7中 Entry的内容大同小异,只是换了个名称而已!
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;  //对key的hashcode值进行hash运算后得到的值,存储在Node,避免重复计算
        final K key;
        V value;
        Node<K,V> next;  //存储指向下一个Node的引用
     
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
     
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
     
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
     
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
     
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

      几个重要属性:

    上一篇:Java垃圾回收机制简述

    栏    目:Ubuntu

    下一篇:Java实现链表的常见操作算法

    本文标题:HashMap实现原理和源码解析

    本文地址:http://www.jh-floor.com/fuwuqijiaocheng/Ubuntu/20199.html

    广告投放 | 联系我们 | 版权申明

    重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

    如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

    联系QQ:888888 | 邮箱:888888#qq.com(#换成@)

    Copyright © 2002-2017 青云站长教程网 版权所有 琼ICP备xxxxxxxx号