黑马程序员技术交流社区

标题: 什么是HashMap？ [打印本页]

---

作者: wk020510    时间: 2019-5-31 15:01
标题: 什么是HashMap？
什么是HashMap？

可以分开来看：

- Hash：散列将一个任意长度通过某种（hash函数算法）算法转换成一个固定值。位移算法（hashCode算法）
- Map：通过hash出来的值，通过该值定位到map，然后value存储到这个map中基本原理



1.HashMap与HashSet的区别

简单回答：HashMap的key就是HashSet

                原因：【HashMap】                实现Map接口，Map采用（key   value）键值对，使用put方法进行数据保存，hashMap使用键对象计算HashCode值，通过唯一的key，可以快速获取对象值；

                                        【hashSet】                实现Set接口，Set是个数组，用add方法存入数据中，而HashCode的值是通过成员对象，进行equals方法比对，获取的值可能相等

---

2.HashMap的底层数据结构

1.7:数组+链表                        头插

1.8:数组+链表+红黑树                        尾插

---

HashMap如果遇到相同的Key，怎么处理？

key值不变，value覆盖：

    public V put （K key ，V value）{
        if(table==EMPTY_TABLE){
            inflateTable(threshold);
        }
        /**这里是采用PutForNullKey处理null值null键*/
        if (key == null)  
        return putForNullKey(value);  
        
    由于HashMap没有Synchronize，所以存在线程安全问题

HashTab：不会处理，在源代码中，发现value为null，就抛出null异常;

                                        但是有Synchronize修饰，不存在线程安全问题；

他的hash冲突算法是:

                        (hash&0X7FFFFFFF)%tab.length:

好比值为16；取值就在0~15之间；

    public Synchronize v put (K key,V value){
            if(value==null){
        thorw new NullPonterException()
            }
    }

---

3.HashMap的数组长度为啥必须是2 的N次幂？

- 保证让key能够落在数组的每一位上
  - 2的N次幂                初始长度16
- 保证-1必定为奇数

---

4.Hash冲突算法的原理分析

- (n-1)&HashCode:     数组长度-1  &  hashCode
  - n-1:   数组长度必须是2*N次幂，-1必定为奇数
    - 进行-1操作后，得到的最后一位必定为1；
    - 进行 ^ 操作时，1&1=1奇数;1&0=0偶数;
    - 那么控制最后的值就取决于HashCode值，保证该参数可落在奇数位上，也可以在偶数位上；
  - HashCode：取key的高16位与低16位【左低右高】进行 ^(异或)操作
    - ^    相同情况下，保证0,1平均的可能性最大
    - 为了上32位的HashCode值，尽可能的参与运算：防止极端情况出现

---

5.HashMap什么时候将链表转换成红黑树

                链表长度                           >=   8;

        HashSet规则：

1.         调用HashCode方法，判断位置上元素hashCode值是否有
   1. 有，调用eqauls方法
      1. 相等：不存；
      2. 不同：覆盖重写
   2. 无，直接保存

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        链表[] 链表对象
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        // 判断数组的长度是为 空或者0 ，数组现在还未初始化
        if ((tab = table) == null || (n = tab.length) == 0)
        
            // resize : 1.初始化   2.进行数组的扩容
            // 通过resize 初始化完毕后，求得数组的长度 并复制给 n
            n = (tab = resize()).length;
            
            
        //存放节点情况一： 计算出来的索引值上并不存在元素-->直接将这个key 放在数组上
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            
            //key相等，value覆盖
        else {
            Node<K,V> e; K k;
            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 {
                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   8
                            treeifyBin(tab, hash);
                        break;
                    }
                    
                    //如果有，不保存
                    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;
    }

                       

    final Node<K,V>[] resize() {
        
        Node<K,V>[] oldTab = table;
        //初始化情况只能是 0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        阈值 扩容临界条件 // 0
        int oldThr = threshold;
        
        
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            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;        //16
            newThr = (int)(DEFAULT_LOAD_FACTOR * //1<<<4        16
                           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"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;



ConcurrentHashMap：

1.7：segment（分段锁）

1.8：transaction 保证序列化：在初始化时用到【和volatile（内存可视化，保证是最新的线程）】

    >>>2   二进制代码右移动   --->n-(n>>>2)                初始化；放值
    所谓的便宜，就是数转换成2进制下，左右移动

---



ConcurrentHashMap：和HashMap的区别

Hashmap线程不安全；在多并发下，put操作会引起【死循环】

HashTable线程安全，由于大量使用synchronize，不能进行多并发操作（不能处理null值；null键）

ConcurrentHashMap处理并发环境下，通过使用大量volatile；final；CAS线程安全问题；【不能处理null值；null键】

阈值计算：HashMap------------------0.75*16

                                        conc urrentHashMap----------------n-(n>>>2);

加synchronize时机：

- HashMap：执行HashCode算法和链表挂载时，将整个线程锁上
- concurrentHashMap：执行HashCode算法和链表挂载时，只将要添加的的链表锁上【锁细化】

【扩容：】{NCPU 类------->cpu的核数/性能---->将线程分成16的倍数----->stride(步伐)：最少为16}

---

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

黑马程序员IT技术论坛 X3.2