A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© wk020510 初级黑马   /  2019-5-31 15:01  /  857 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

什么是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}

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马