53 HashMap8 源码解读

作者: 滔滔逐浪 | 来源:发表于2020-09-12 10:18 被阅读0次

53 HashMap8 源码解读
AFN 3.0学习总结（最后的总结转载）
spring源码解读网上知识摘要
文章目录
Element分析（组件篇）——TableHeader
JDK源码-Object
【Java源码计划】LongAdder<rt.jar_ja
AFNetworking 3.0 源码解读（五）之 AFURLS
java多线程
AFURLSessionManager

1，为什么重写equals还要重写hashcode方法
hashcode方法：底层采用c语言编写的，根据对象内存地址转换成整数类型。
如果2个对象的hashcode值相等的情况下，则对象的内容值不一定相等
如果使用equals方法比较2个对象内容值相等的情况下则2个对象的hashcode值相等。
注意： equals 方法默认的情况下object类中采用==比较对象内存地址是否相等。
hashmap 地层中equas 和hash 值，set

关于hashcode和equals的处理。遵循以下规范：1）只要覆写equals就必须覆写hashcode。2}因为set 存储的是不重复的对象，依据hashcode和equals进行判断，所以set 存储的对象必须覆写这个方法。3）如果自定义对象作为map键，那额必须覆写hashcode和equals .说明：String已经覆写hashcode和equals方法。所以我们可以愉快的使用String对象作为key来使用。

hashMap 如何避免内存泄漏的问题
内存泄漏：
HashMap 集合中是否可以存放自定义的key:
自定义对象作为key的时候，一定要重写equals和hashCode保证对象 key不被重复创建。

HashMAp和HashTable
HashMap 线程不安全，允许存放key为null ,放在数组0的位置

HashMap 底层如何实现：
1，基于arraylist集合方式实现
优点不需要考虑hash 碰撞的问题：
缺点：时间复杂度为o(N)

image.png

package com.taotao.lizi.hashmap.map;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * 基于Lists数组存放
 * @author aping
 * @time 2020/9/12 11:19
 */
public class ArrayListHashMap<K, V> {
    private List<Entry<K,V>> entrys=new ArrayList<>();

    class Entry<K, V> {
        K k;
        V v;

        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }

    public void put(K k, V v) {
     entrys.add(new Entry<K,V>(k,v));
    }

    public V get(K k) {
        for (Entry entry:entrys ) {
            if(entry.k.equals(k)){
                 return  (V)entry.v;
            }
            
        }
        return  null;
    }


    public static void main(String[] args) {
         ArrayListHashMap<Object,String>arrayListHashMap=new ArrayListHashMap<>() ;
         arrayListHashMap.put("a","a");
         arrayListHashMap.put(97,"97");
        System.out.println(arrayListHashMap.get("a"));
        System.out.println(arrayListHashMap.get(97));
    }
}

2，基于数组+链表方式（jdk1.7）
hashMap中如果么有发生碰撞的问题，get查询的时间的复杂度是o(1),直接根据下标查询。

hash 碰撞的问题：（hash值相同，内容不同）
解决办法： jdk1.7采用链表存放、

package com.taotao.lizi.hashmap.map;

/**
 * 数组加链表
 *
 * @author aping
 * @time 2020/9/12 12:08
 */
public class ExthashMap<K, V> {
    private Entry[] entrys = new Entry[10000];

    class Entry<K, V> {
        K k;
        V v;
        Entry<K, V> next;

        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }

    public void put(K k, V v) {
        //数组加链表实现hash算法
        int index = k==null?0: k.hashCode() % entrys.length;
        //判断key是否冲突
        Entry oldEntry = entrys[index];
        if (oldEntry == null) {
            //key没有发生hash碰撞的问题
            entrys[index] = new Entry<K, V>(k, v);
        } else {
            oldEntry.next = new Entry<K, V>(k, v);
        }
       // entrys[index] = new Entry<K, V>(k, v);
    }

    public V get(K k) {
        //数组加链表实现hash算法
        int index = k==null?0: k.hashCode() % entrys.length;
        for (Entry oldEntry = entrys[index]; oldEntry != null; oldEntry = oldEntry.next) {
            if ((k==null&oldEntry.k==null)||oldEntry.k.equals(k)) {
             //    System.out.println((V) oldEntry.v);
                return (V) oldEntry.v;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ExthashMap<Object, String> hashMap = new ExthashMap<>();
        hashMap.put("a", "a");
        hashMap.put(97, "97");
        System.out.println(hashMap.get("a"));
        System.out.println(hashMap.get(97));
    }
}

3，基于数组+链表方式+红黑树(jdk1.8)
HashMap类似容器，使用Entry存储对象

时间复杂度：
o(1) 只需要查询1次。使用数组index查找。
查找 Array[1]：效率非常高。
o(n)，循环从头到尾部，查询效率非常低。
o（logn）:平方，二叉树，红黑树效率还可以。

HashMap 底层是有序还是无序存放的？

无序散列存放，不保证连续

LinkedhashMap 和TreeMap 底层如何实现有序的？
底层实现双向链表头尾相连。

image.png

HashMap基础知识
HashMap与HashTable之间的区别
1，HashMap实现不同步，线程不安全。 HashTable线程安全 HashMap中的key-value都是存储在Entry中的。

2，继承不同。
　　Hashtable 继承 Dictionary 类，而 HashMap 继承 AbstractMap
　　public class Hashtable extends Dictionary implements Map
　　public class HashMap extends AbstractMap implements Map

3， Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，
但是要使用HashMap的话就要自己增加同步处理了。

4， Hashtable 中， key 和 value 都不允许出现 null 值。在 HashMap 中， null 可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为 null 。
　　当 get() 方法返回 null 值时，即可以表示 HashMap 中没有该键，也可以表示该键所对应的值为 null 。因此，在 HashMap 中不能由 get() 方法来判断
　　HashMap 中是否存在某个键，而应该用 containsKey() 方法来判断。

5，哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值

HashMap如何避免内存泄漏问题
HashMap面试题
为什么重写Equals还要重写HashCode方法
HashMap如何避免内存泄漏问题
HashMap1.7底层是如何实现的
HashMapKey为null存放在什么位置 0
HashMap如何解决Hash冲突问题
HashMap底层采用单链表还是双链表单向链表
时间复杂度O(1)、O(N)、O(Logn)区别
HashMap根据key查询的时间复杂度
HashMap如何实现数组扩容问题
HashMap底层是有序存放的吗？
LinkedHashMap 和 TreeMap底层如何实现有序的

HashMap底层如何降低Hash冲突概率
HashMap中hash函数是怎么实现的？
为什么不直接将key作为哈希值而是与高16位做异或运算？
HashMap如何存放1万条key效率最高
HashMap高低位与取模运算有那些好处
HashMap1.8如何避免多线程扩容死循环问题
为什么加载因子是0.75而不是1