黑马程序员技术交流社区

标题: 【成都校区】HashMap源码追踪 [打印本页]

作者: 小刀葛小伦    时间: 2019-10-10 16:51
标题: 【成都校区】HashMap源码追踪
1.HashMap简介
HashMap作为开发中使用频率比较高的容器类,对HashMap底层原理的理解。有利我们写出质量更高的代码,提升系统的性能。

2.从类的层次看HashMap
HashMap实现Map接口,属于集合框架中Map的一种实现,主要使用key和value存储数据。存储的元素key是不可以重复,重复的情况下,进行覆盖。
HashMap 属于线程不安全的类,在并发的情况下。同一时刻同一个HashMap,一个线程向HashMap 中put元素,另一个线程迭代HashMap中的元素会产生fast fail。程序会抛出异常。
3.构造函数以及常用的Api
3.1 构造函数
   /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

无参构造函数,初始化HashMap哈希表默认的长度为16 负载因子为0.75

  /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

有参构造函数,initalCapacity用于初始化哈希表的长度,负载因子的初始化0.75。由于哈希表需要扩容,所以能够确定HashMap中存储数据多少的情况之下。创建HashMap的时候,建议指定HashMap的大小。

/* ---------------- Public operations -------------- */

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

可以指定HashMap初始化哈希表的长度,和负载因子的大小。由于负载因子0.75 刚好效率最好,开发中一般不建议,指定负载因子的大小。

  /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

传入实现Map的集合类,可以完成集合中数据的复制。

3.2 常用api
3.2.1 HashMap 主要用于数据的增删改查,所以常用的Api主要按照增删改查进行分类
增加元素: put(K key, V value),putAll(Map<? extends K, ? extends V> m)
删除元素:remove(Object key),remove(Object key, Object value),clear()清空元素
修改元素:值覆盖的方式修改value,直接使用put(K key, V value)方法,replace(K key, V value),replace(K key, V oldValue, V newValue)。
查询:(1)查询容器本身:size(),isEmpty(),(2)查询容器中的元素:get(Object key), entrySet() , keySet(),values() 。
4. 源码追踪
4.1 put 元素的过程
  /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

(1)put元素的时候,先根据key计算,存储元素所在哈希表中的下标。key为null时存储的下标为0,通过key的hashcode进行计算后,得出下标。这种计算得到的下标冲突比较的少。但是也有可能产生下标的冲突。
下标冲突之后,通过下标中的链表解决冲突的问题。

(2)扩容问题:负载因子大小对扩容的影响
负载因子越小,由key计算的哈希表的下标冲突的可能性越小,扩容的次数越多
负载因子越大,由key 产生的哈希表的下标冲突的可能性越大,扩容的次数越小

5. 这么重要的类,JDK 肯定在不停的优化它
Java8中对于hash冲突,哈希表中同一个下标的元素,超过8的,不在使用链表的数据结构进行存储,直接使用红黑树进行存储数据。
2.红黑树数据结构:比较不错的红黑树文章
6.使用HashMap注意问题总结
扩容很消耗性能,确定HashMap存储元素的多少时候,初始HashMap 时候指定大小。
HashMap 是线程不安全的类,多线程的情况下,容易造成死循环。导致Cpu飙升。






欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2