文档章节

HaspMap

妹子快加微信
 妹子快加微信
发布于 2017/08/14 22:30
字数 5685
阅读 46
收藏 1

Base:JDK1.8

1、HashMap

在常用的数据结构中,有链表,数组,哈希表,树等几种数据结构,由于数组和链表是两种极端(当数据量较大,且插入的位置靠前),数组插入的时候,需要进行arraycopy,因此空间上也是一种浪费,效率也会降低,而链表,如果去查找某个数据的时候,又需要从头到尾的遍历,因此,这两种数据结构是存在一些缺陷的,但是不可否认是非常好用的两种结构。

于是为了平衡,进行了一个折中的处理,采用 数组+链表 的结构进行存储。

为什么叫做哈希表呢,因为这里面关键的存储方法中使用了  hash算法。

之前想着细致,不过自己读了一遍,发现那算是啰嗦了,因此以后写出比较关键的地方。

2、继承的类和实现的接口

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

从代码中可以看出来实现的是map接口,而不是 ArrayList和linkedList 中的 List接口。因此我们常常会问的一个题目就是,map 是否实现了Collection接口(Collection接口是List的父接口)?

答案是没有的。

实现了 Collection 接口的类有: ArrayList、LinkedList、HashSet、TreeSet 这几个最常见的。当然还有其他的,等写完全部的时候,我去偷一个族谱传上来吧。

3、HashMap中的成员变量、数据结构、常用方法

3.1、成员变量

/**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
 transient Set<Map.Entry<K,V>> entrySet;

之前只知道HashSet 用的 HashMap的数据结构,今天看到HashMap中又使用到了Set的接口。。。

有点迷。

为了方便理解,贴上英语吧,cached 应该是缓存的意思。。

拥有缓存的entryset()

其实这个HashMap 中这个缓存我第一次看到,也不知道用法,以前从来没有注意过啊~~

 transient int size;

表示大小。

 /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

这个应该是 下次扩容是的 大小吧。

一直以为它扩容就直接扩了,原来还有记录下一次的。。。。

 /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

人称 负载因子 。。。听着很厉害的样子,其实就是记录,什么时候扩容,别名是一个阈值(yuzhi),以前竟然一直以为是fazhi。。。。就是当 size/table.length  如果大于或者等于 了 loadFactor ,就代表着达到了这个map的阈值,需要进行resize扩容了。(其实等于是否扩容,我不知道,瞎说的哈哈。)

3.2、常量

   /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

设定初始化长度的,如果我们只new 一个HashMap,没有指定长度,就会生成一个数组长度为 16 的。

为什么不直接写个16 。而非写个 1<<4  (二进制 :000001 右移操作====二进制: 0010000 ===16)?

英语:默认的初始化长度, 必须是2的整数 幂 呢?

问题:为什么非得是2的 整数  幂 呢????这个跟 hash算法,跟put,get等方法都有关系,把答案写到最后的总结吧。

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

最大的容量,。

英语第三行: 必须是2的整数 幂,且 小于等于 1 然后 右移30位。

这个就是限制一下 HashMap底层数组的最大length 。

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

默认的 负载因子 是 0.75 ,也就是说,当size 存到 四分之三的时候就进行扩容。

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

这三个放一块,其实我也不知道他们的作用是啥。。。。。先放着吧,不过 看 第二行

the bin。。 说一个 哈希表中的一个 常用术语:  bucket  桶。

这个我也是在后面学到 多线程,currentHashMap中才看到的一个概念,为了将来,提前说吧:

 

什么是bucket?

bucket的英文解释: 

Hash table lookup operations are often O(n/m) (where n is the number of objects in the table and m is the number of buckets), which is close to O(1), especially when the hash function has spread the hashed objects evenly through the hash table, and there are more hash buckets than objects to be stored. 

可以这样理解:

一个HASH的结果所对应的地址可存放两个BUCKET。可解决HASH冲突。 

  • 要存数据时,第一次HASH到这里,在第一个BUCKET存放一个数据。 
  • 要存数据时,当第二次因某些原因HASH到这里时,在第二个BUCKET存放另一个数据。  

更直观的体现:

每一个红圈都是一个桶。

ps;是否 达到  根据  size 去衡量的,而不是 非空桶去 衡量的,没有数据的是空桶比如 4 ,5,6,7。

3.3、数据结构

 transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */

底层的数据结构是一个Node数组,关于Node类:

**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        //哈希值,具体的这几个使用到哈希算法的集合中,哈希算法都重写了,有区别的
        final int hash;
        //key值,也就是你存储对象的别名吧。暂时这么理解,这个属于唯一不可重复的。
        final K key;
        //真正存你的数据的地方。
        V value;
        //下一个节点的引用,因为哈希表是一个数组+链表的组合。
        Node<K,V> next;
       // 构造方法。
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

其实这个Node是一个 静态内部类,是存在于HashMap中的,图来自百度,图侵删。

(以前没注意,这次看了看类,发现里面的内部类好多啊!!!!!就写个我知道的吧,其他的真是用过但是没去仔细看过,等看过再添加一下)

图:

其实我感觉这个图还不是很准确吧,

感觉0 -15 也应该存的有节点的。这个图仅供 参考理解吧。

3.4 常用方法

3.4.1 构造方法

3.4.1.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
    }

默认 初始化 第一次长度 是16,负载因子是 0.75,不过我也没见他底层数组进行初始化啊~~

3.4.1.2 带长度的构造方法

/**
     * 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);
    }

这个是可以指定长度的构造方法,不过建议初始化 的长度 是2 的整数倍 。 负载因子是默认的 0.75。

3.4.1.3 带长度,负载因子的构造方法

    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);
    }

上个方法 调用的是这个方法。

这个方法 支持自定义长度 跟自定义 负载因子。

不过 还是建议 长度 是2 的整数倍, 负载因子真的不建议去改,除非是大牛,自己去切身体验过设么时候resize最好。

3.4.1.4 传入一个Map的实现子类的集合

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

 这个是传入一个 map 的子类,然后转换成一个 HashMap, 我是没怎么用过。。

高能预警

3.4.2 put方法

由于 HashMap是以 Key----Value , 这种一对 一对出现的,所以put方法就必须传入两个参数。

谨记Key 是不允许重复的,Value可以。

以下是 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);
    }

在这个里面,传入两个参数, 而且内部条用了 hash方法,跟 putVal方法。

首先介绍hash方法,比较核心的。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这个方法写的非常简洁,三目表达式。

首先判断key 是不是 null, 如果是直接返回 0

如果不是 ,就进行运算。

我们都知道,每个类都是继承自Object  方法,因为Object类中 写了hashCode 方法。

代码贴上:

public native int hashCode();

有的类重写了此方法,比如String类中的

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

比如Integer 类中的 hashCode方法:

 public int hashCode() {
        return Integer.hashCode(value);
    }
 public static int hashCode(int value) {
        return value;
    }

这都重写了方法。

不过一般都是String 做Key 的吧。。

其他的类就不列举了,有兴趣就自己瞅瞅,应该都有自己的写法。

如果没有冲写,这个类 就会调用父类的 hashCode 方法, 最不济就是Obejct 调用本地的 HashCode方法。

 

回归正题:

拿 String为Key 来讲解吧:

 

/**
*将上面的代码进行分步,更加便于理解
*
*/
int h=key.hashCode();
//这个用人话就是 h和h/2的16次方的数 进行 与运算
int hash=  h^h>>>16;
return hash;

为什么这么算呢?

首先, 我们知道 HashMap 是无序的,同样是效率非常高的, 这是为什么呢,就是因为他实现它的存放的时候,不是像ArrayList 或 LinkedList 那样子 obejct[size++] 或者 往表尾直接添加一个 节点。

他存放的位置 直接就是 找一个 数 , 作为他的下标 存到底层的数组中,如果取的时候,直接再通过这个下标 进行取就行了。

那么怎么去 找这么一个数字呢 ,那就是hash算法的事情了。

然后讲解 hash算法为什么这么写:

我们知道,底层是数组,要找一个 下标  存这个节点,当然那需要 这个 数字 还不能 大于 数组的长度,

用 hash%table.length   是最好的,得到的数字肯定不会大于 数组长。

 

首先我先打印几个:

就打印2个吧,发现了吧,这个数字挺大的。。

如果你让他去 %table.length  , 估计 计算机 也是挺难受的。 这是 我大学 学哈希表的时候 求 index 的方法。)

 

我的方法求一个 index和用jdk的方法求一个index方法进行比较:

 

很厉害,很神奇,我们都知道 计算机中的 位运算 是效率比较高的运算。

这样子,很神奇 效果 一毛一样。。

 细心的同学会发现,  这两个图的 11 行 hashCode&15

为什么是 15 呢?  第10行 %16 ?

这都是为什么呢?

这就不的不提 上面的 一直强调的 为什么 底层数组的长度是2的整数 幂

现在稍微总结和解释:

知乎专栏: https://zhuanlan.zhihu.com/p/21673805

方法一:
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


方法二:JDK1.8没有这个方法  切记,切记,之前面试问我,我还回答有。。都记混了。。
static int indexFor(int h, int length) {  
   //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的 
   // jdk1.8中是在put的时候,直接使用的 h&(length-1)的,而不是写了一个方法
     return h & (length-1);  //第三步 取模运算
}

这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算

对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,模运算的消耗还是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙,它通过h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

求余数的过程图解:

我们都知道 2的整数 幂 肯定是  10 ,100,1000,10000 只有一个1 ,

对 上图稍微改进一下:

当 n为 2的整数幂的时候,

所有高位(就是在 n 这个 唯一 的 1 前面数肯定能 整除 ):

 

而 1 的右边的 四位 肯定是除不尽的。

这样,所以 1 位置 的 右边 后四位,2进制 换成 10进制,就完美的是 余数。

因此, 将 table.length -1 后 与  hash 进行 & 运算:

很快就 计算出来余数。

跟取余 的效果 一毛一样,而且 速度快。

延伸: 当除数是2的 整数幂的时候, 求商,可以直接使用 >> 右移计算,这也是比普通除法快的。

比如: 12231/8  == 12231>>3       8 是 2 的3次方, 因此右移3个,几次方 就是左移几次。

 

接下来是put 的 方法代码:

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
       //首先判断table 是不是空,或者是不是为null
        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<K,V> e; K k;
           // 如果已经存在数据了,就去遍历这个桶的 链表进行比较。
         
            // 先判断 这个点的 hash 是否一样,如果一样比较key 的地址,最后使用equals方法比较
           //注意几点:hash一样,key不一定一样(几率特小)
           // key一样,hash肯定一样(计算方法一样,肯定一样)
           // == 一样,表示是同一对象,肯定equals 一样。
          // 这里面  有  短路  现象, 自查~ 
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                 //如果符合条件,就得到这个 节点 的引用
                e = p;
            else if (p instanceof TreeNode)
               //说实在,这个不是太明白为什么
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //接下来是遍历链表查找,表中的 key是否已经存在,
                for (int binCount = 0; ; ++binCount) {
                    //先指向下一个节点,如果是null,就将 node 放入到这里,
                   //第一个节点已经判断过了,这种方式类似do{}while()吧。
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 判断条件同上
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果 e 是存在的,也就是说,key值已经 存过了
             // 这就是 为什么 HashMap为什么不能存重复key 的原因了!
            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;
    }

这个方法写的贼多。。。。

3.2.3 resize

接下来是扩容方法:

 final Node<K,V>[] resize() {
    	//记录扩容前的Hash表
        Node<K,V>[] oldTab = table;
        //记录扩容前数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //这下面是判断 扩容前的长度是否是一个 异常的长度
        if (oldCap > 0) {
        	  //如果扩容前的长度超过了 规定的最大的长度
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //扩容前的长度  *2 是否 超过规定的最大值(这扩容也是每次都是 2被,初始化 是 16,每次都是2倍,
            // 扩容后还是2的 整数幂
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
               
        }
        // 这一堆 判断 就不看了。。
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
          //初始化一个table 
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
         //判断 扩容前的表是不是一个null 的,如果是null,就不用数据复制了。
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果 当前桶 不为空
                if ((e = oldTab[j]) != null) {
                	//将桶制空,当所有桶都空,方便gc回收
                    oldTab[j] = null;
                    if (e.next == null)
                    	//再次用hash值进行求一个 index 
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                    	//如果当前桶 有一个链表
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        
                        do {
                            next = e.next;
                            //这里为什么这么处理???
                            if ((e.hash & oldCap) == 0) {
                            	//这个判断如果 是不是 空,不是空,就接着组成一个链表
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //把分好类的 放入到 新的table 数组中
                        //我们发现 如果之前的 hash&length ==0 就放入newtable[j]
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                      //我们发现 如果之前的 hash&length !=0 就放入newtable[j+oldCap]
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

resize 也是一个大工程

其实主要的没什么看的,就是 新new 一个 table[] 然后 进行数据转移就好 。

扩容是 resize 前的2倍,这样就能 是2的 整数幂 进行扩容了。

如果仔细看的 同学, 会 有一个 地方 就是

我在里面注释的 这里为什么处理??? 这应该就是数据转移的

很神奇 啊。 稍微 研究了一下:

首先 上一个 比较神奇的图:

 

再来一个:

大家发现没:

就是  hashCode&16+hashCode&15(也就是代码中的 j  ,因为这个j就是代表 桶的 index)

就====  hashCode&31    这很强大啊 ,

接下来数学角度分析一波、

还是之前的图:

 

前 2  的 结果相加  就是 第三个。。。

难道 &运算还符合 结合律吗???

有上面的图 很清晰的看出来, 其实 (2n-1)&hash  就是 等于 是    (n&hash)+((n-1)&hash)

当然 n 肯定是 2 的整数幂、、

不得不说, 这东西,非常厉害。

 

3.2.4 remove

put方法就是核心,讲解完了之后,后面的应该都不是问题:

根据key 进行 remove

 public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

remove 内层调用方法


    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
       //判断标是不是空, 同时判断 表长是不是 大于 0, 还有 直接使用 hash算法求得桶的第一个是不是null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            //先判断第一个点,判断方法相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                  //不知道什么意思
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                  //从第二个点开始 遍历 判断是否存在 相同key
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
             //如果找到了 这个节点(不是null),就进行移除。
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

3.2.5 get

 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

内层调用的方法:

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            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<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

get 方法是同样的套路,都是 遍历查找,用的判断条件也都一样,hash,下表的求法都大同小异,偷个懒,这些都不用去解释了吧。

3.5 其他方法总结

是否包含对应的key public boolean containsKey(Object key)
是否包含对应的value public boolean containsValue(Object value)
放入一个map的子类  public void putAll(Map<? extends K, ? extends V> m)
返回size public int size()
返回是否为空 public boolean isEmpty()
   
   
   
   
   

总结:

其实 HashMap 没有什么神秘的。

底层就是 数组+链表

就是放入的时候 看我的解释,put方法的流程,什么时候使用equals, 什么时候使用 hashCode,为什么扩容是2的幂?

到后来 看了 HashSet 的源码后,还要知道,hash计算方法有什么不同,为什么要重写hash方法?

HashMap 为什么不能重复? (put 方法第一行就处理了,是null得 hash值是 0 )

大体的 知识点应该就是这些吧。如果有补充就告诉我~~欢迎~

-----------------------------------------------------------------------------

不保证代码完全正确,也不保证代码是最优。

仅仅是根据自己的理解,写出来直观的代码,方便理解。

错误请指出,感激不尽!

 

© 著作权归作者所有

上一篇: HashSet
下一篇: LinkedList
妹子快加微信
粉丝 1
博文 18
码字总数 26224
作品 0
洛阳
私信 提问
jsonObject 解析map 字段问题

之前解析map的时候一般都是 Map<String, String> param = new HashMap<String, String>(); String signature = JSONObject.fromObject(param).toString(); 但是今天发现这样子解析出来的额 ......

狮子暴走
2015/08/02
547
5
ArrayList 和 HaspMap 链式添加的实现

一、背景 在application中ArrayList 和 HaspMap 这两个类是经常用到的。而且,一般需要处理的数据量也不会少,因为这两个类是没有实现链式添加元素的,因此我们需要不断重复的编写这两个类声...

_魔术师_
2013/11/13
472
0
Java 容器 & 泛型:五、HashMap 和 TreeMap的自白

Writer:BYSocket(泥沙砖瓦浆木匠) 微博:BYSocket 豆瓣:BYSocket Java 容器的文章这次应该是最后一篇了:Java 容器 系列。 今天泥瓦匠聊下 Maps。 一、Map回顾 Map,又称映射表,是将键映...

泥沙砖瓦浆木匠
2015/05/05
1K
0
HaspMap 多线程下 resize 死循环

HashMap在多线程下面出现死循环,这种情况有点难模拟,千万别在生成环境出现,一旦出现那就等着哭吧。 废话不多说不知道hashmap 如何扩容的先看下源码可能好理解点。 void resize(int newCap...

smallsun512
2013/12/26
508
0
Java中HashMap遍历

在Java中有多种遍历HashMap的方法,注意Java中所有的Map类型都实现了共有的Map接口,所以接下来方法适用于所有Map(如:HaspMap,TreeMap,LinkedMap,HashTable,etc) 方法1 使用For-Each迭代...

fromradio
2016/08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部