Hefery 的个人网站

集合作用

集合：对象的容器，定义了对多个对象进行操作的常用方法

集合按照其存储结构可以分为两大类：单列集合java.util.Collection、双列集合java.util.Map

集合与数组的区别：

Collection

Collection是所有单列集合的父接口，在Collection中定义了单列集合(List和Set)通用的方法，这些方法可用于操作所有的单列集合

public class CollectionTest {
    public static void main(String[] args) {
        // 创建集合对象，可使用多态
        Collection<String> cell = new ArrayList<>();
        System.out.println(cell);  //重写了toString方法

        // 添加元素 add(E e)
        boolean b1 = cell.add("Hefery");
        System.out.println(b1);   //true,无需接收返回值
        System.out.println(cell); //[Hefery]

        cell.add("Hello");
        cell.add("World");

        // 移除元素 remove(Object o)
        boolean b2 = cell.remove("World");
        boolean b3 = cell.remove("abc");
        System.out.println(b2);  //true
        System.out.println(b3);  //false

        // 查询元素 contains(Object o)
        boolean b4 = cell.contains("Hefery");
        boolean b5 = cell.contains("Woorld");
        System.out.println(b4);  //true
        System.out.println(b5);  //false

        // 判空 isEmpty()
        boolean b6 = cell.isEmpty();
        System.out.println(b6);  //false

        // 元素个数 size()
        int b7 = cell.size();
        System.out.println(b7);  //2

        // 集合元素存入数组 toArray()
        Object[] arr = cell.toArray();
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }

        // 清空 clear()
        cell.clear();
        System.out.println(cell);  //[]
    }
}

List

List特点：

1. 有序的 collection（也称为序列）
2. 带索引，有下标
3. 允许重复的元素

List的常用子类：

• ArrayList 底层结构是数组,底层查询快,增删慢
• LinkedList 底层结构是链表,增删快,查询慢
• Voctor 底层结构是数组,线程安全,增删慢,查询慢

ArrayList

public class ArrayList<E> extends AbstractList<E> implements List<E>

底层：数组
特点：查询快，增删慢，线程不安全
必须开辟连续空间

重要方法

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class listDemo {
    public static void main(String[] args) {
        //创建 List 对象(多态)
        List<String> list = new ArrayList<>();

        //添加元素
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("a");
        System.out.println(list);

        //添加元素，在指定位置
        list.add(3,"d");
        System.out.println(list);

        //移除元素(位置)
        list.remove(3);
        System.out.println(list);

        //替换元素值
        list.set(3,"A");
        System.out.println(list);

        //遍历
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }

        for (String e:list) {
            System.out.println(e);
        }

        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            String s0 = it.next();
            System.out.println(s0);
        }
    }
}

源码分析

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /** 默认容量 */
    private static final int DEFAULT_CAPACITY = 10;

    /** 数组元素 */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /** 默认空数组 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /** 存放元素 */
    transient Object[] elementData; // non-private to simplify nested class access

    /** 元素个数 */
    private int size;

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }
  
    /** 无参构造 */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
  
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    /** 数组扩容：如果没有向集合中添加任何元素时，容量0，添加一个元素之后容量10，默认长度是10，当超过长度时，按50%延长集合长度 */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
  
}  

LinkedList

底层：双向链表
特点：查询慢，增删快，线程不安全
无需开辟连续空间

重要方法

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class listDemo {
    public static void main(String[] args) {
        demo01();
    }

    private static void demo01() {
        //创建 LinkedList 对象(不能使用多态)
        LinkedList<String> linkedlist = new LinkedList<>();

        //添加
        linkedlist.add("a");
        linkedlist.add("b");
        linkedlist.add("c");

        linkedlist.addFirst("www.");
        linkedlist.addLast(".cn");

        linkedlist.add(1,"hefery");

        linkedlist.push("lalala");

        System.out.println(linkedlist);  //[lalala, www., hefery, a, b, c, .cn]

        //获取
        System.out.println(linkedlist.getFirst()); //lalala
        System.out.println(linkedlist.getLast());  //.cn
        System.out.println(linkedlist.get(2));     //hefery

        //移除
        linkedlist.removeFirst();
        linkedlist.removeLast();
        linkedlist.pop();
        System.out.println(linkedlist);  //[hefery, a, b, c]

    }
}

源码分析

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

	/** 集合大小 */
    transient int size = 0;

    /** 链表头结点 */
    transient Node<E> first;

    /** 链表尾节点 */
    transient Node<E> last;

    /** 空参构造 */
    public LinkedList() {
    }
  
    /** 节点结构 */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
  
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
  
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

}

Voctor

Vector 类可以实现可增长的对象数组，线程安全
底层：数组
特点：查询快，增删慢，线程安全

重要方法

Set

HashSet

底层：哈希表，基于 HashMap 实现的
特点：不包含重复元素，无索引，无序

重要方法

//存储自定义类型元素，需重写 hashCode() 和 equals() 
import java.util.HashSet;
/*
    重写 hashCode() 和 equals() 保证同名同龄的人只能存储一次
 */
public class hashCodeDemo {
    public static void main(String[] args) {
        HashSet<Person> set = new HashSet<>();

        Person p1 = new Person("Hefery",22);
        Person p2 = new Person("Hefery",22);
        Person p3 = new Person("Hefery",18);
        System.out.println(p1.hashCode());  //未重写:356573597     重写后：-1830346093
        System.out.println(p2.hashCode());  //未重写:1735600054    重写后：-1830346093
        System.out.println(p1==p2);         //未重写:false         重写后：false     比较地址
        System.out.println(p1.equals(p2));  //未重写:false         重写后：true

        set.add(p1);
        set.add(p2);
        set.add(p3);

        System.out.println(set);
        //未重写：[Person{name='Hefery', age=22}, Person{name='Hefery', age=22}, Person{name='Hefery', age=18}]
        //重写后：[Person{name='Hefery', age=22}, Person{name='Hefery', age=18}]
    }
}

源码分析

LinkedHashSet

具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现
底层：哈希表(链表+红黑树) + 链表(记录元素存储顺序)

import java.util.HashSet;
import java.util.LinkedHashSet;

public class linkedhashsetDemo {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();

        set.add("www");
        set.add("abc");
        set.add("abc");
        set.add("cn");

        System.out.println(set);  //无序，不允许重复

        LinkedHashSet<String> linked = new LinkedHashSet<>();

        linked.add("www");
        linked.add("abc");
        linked.add("abc");
        linked.add("cn");

        System.out.println(linked);  //有序，不允许重复
    }
}

TreeSet

底层数据结构：红⿊树
特点：
基于排列顺序实现元素不重复
实现了 Sortedset接口，对集合元素自动排序
元素对象的类型必须实现 Comparable接口，指定排序规则
通过 CompareTo方法确定是否为重复元素

Collections

public class Collections extends Object

常用方法

@Data
public class Person implements Comparable<Person>{
    private String name;
    private int age;
    //重写排序规则
    @Override
    public int compareTo(Person o) {
        return  this.getAge() - o.getAge(); //年龄升序
        //return  o.getAge() - this.getAge(); //年龄降序
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;

        if (age != person.age) return false;
        return name != null ? name.equals(person.name) : person.name == null;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

import java.util.ArrayList;
import java.util.Collections;
/*
    注意：sort()使用：在被排序的集合实现必须重写接口中的 compareTo 定义的规则
    compareTo：
        升序：this.参数 - o.参数
        降序：o.参数 - this.参数
 */

public class CollectionsDemo {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();

        //添加多个元素
        Collections.addAll(list,"a","b","c","d","e");
        System.out.println(list);  //[a, b, c, d, e]

        //打乱元素顺序
        Collections.shuffle(list);
        System.out.println(list);  //[e, b, d, a, c]

        System.out.println("===============================");

        ArrayList<Integer> in = new ArrayList<>();
        Collections.addAll(in,12,15,14,13,16);
        System.out.println(in);  //[12, 15, 14, 13, 16]

        //升序
        Collections.sort(in);
        System.out.println(in);  //[12, 13, 14, 15, 16]

        System.out.println("===============================");

        ArrayList<String> str = new ArrayList<>();
        Collections.addAll(str,"lalala","hefery","hahaha","biubiubiu");
        System.out.println(str);  //[lalala, hefery, hahaha, biubiubiu]
        Collections.sort(str);
        System.out.println(str);  //[biubiubiu, hahaha, hefery, lalala]

        System.out.println("===============================");

        ArrayList<Person> p = new ArrayList<>();
        p.add(new Person("lalala",12));
        p.add(new Person("hahaha",8));
        p.add(new Person("wawawa",32));
        System.out.println(p); //[Person{name='lalala', age=12}, Person{name='hahaha', age=8}, Person{name='wawawa', age=32}]

        //重写 compareTo 方法，根据 age 升序
        Collections.sort(p); //[Person{name='hahaha', age=8}, Person{name='lalala', age=12}, Person{name='wawawa', age=32}]

        System.out.println(p);
    }
}

Comparator和Comparable

Comparable：自己this与别人o比较，自己需要实现 Comparable 接口，重写比较规则 compareTo 方法
Comparator：找第三方仲裁

public class CollectionsDemo {
    public static void main(String[] args) {
        ArrayList<Person> p = new ArrayList<>();
        p.add(new Person("lalala",12));
        p.add(new Person("bhahaha",8));
        p.add(new Person("ahihihi",8));
        p.add(new Person("wawawa",32));
        System.out.println(p);
        //[Person{name='lalala', age=12}, Person{name='hahaha', age=8}, Person{name='wawawa', age=32}]

        //重写 compareTo 方法，根据 age 升序
        //Collections.sort(p);
        //[Person{name='hahaha', age=8}, Person{name='lalala', age=12}, Person{name='wawawa', age=32}]

        /*Collections.sort(p, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                //return o1.getAge() - o2.getAge();  //age升序
                return o2.getAge() - o1.getAge();   //age降序
            }
        });*/

        Collections.sort(p, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                int result = o1.getAge() - o2.getAge();
                //age相同，比较姓的首字母
                if( result > 0 ){
                    result = o1.getName().charAt(0) - o2.getName().charAt(0);
                }
                return result;
            }
        });

        System.out.println(p);
    }
}

Map

HashMap<K,V>

底层：数组+链表(Java7)、数组+链表+红黑树(Java8及之后)
特点：无序，存储取出元素顺序可能不一致

重要方法

public class mapDemo {
    public static void main(String[] args) {
        //show01();
        //show02();
        //show03();
        show04();
    }

    private static void show04() {
        /*
             boolean containsKey(Object key)
                如果此映射包含指定键的映射关系，则返回 true
         */
        Map<String,Integer> map4 = new HashMap<>();

        map4.put("赵丽颖",168);
        map4.put("林志玲",178);
        map4.put("刘洋",188);

        System.out.println(map4);

        boolean v1 = map4.containsKey("赵丽颖");
        System.out.println("v1:" + v1);  //v1:true
        boolean v2 = map4.containsKey("赵颖");
        System.out.println("v1:" + v2);  //v1:false
    }

    private static void show03() {
        /*
             V get(Object key)
                返回指定键所映射的值；
                如果此映射不包含该键的映射关系，则返回 null
         */
        Map<String,Integer> map3 = new HashMap<>();

        map3.put("赵丽颖",168);
        map3.put("林志玲",178);
        map3.put("刘洋",188);

        System.out.println(map3);

        Integer v1 = map3.get("刘洋");
        System.out.println("v1: " + v1);
    }

    private static void show02() {
        /*
             V remove(Object key) ：
                返回值：V
                    Key 存在，返回被删除值
                    Key不存在，返回null
         */
        Map<String,Integer> map2 = new HashMap<>();

        map2.put("赵丽颖",168);
        map2.put("林志玲",178);
        map2.put("刘洋",188);

        System.out.println(map2);

        Integer v1 = map2.remove("林志玲");
        System.out.println("v1:" + v1);  //v1:178
        System.out.println(map2);

        Integer v2 = map2.remove("林志颖");
        System.out.println("v1:" + v2);  //v1:null
    }

    private static void show01() {
        /*
            put(K key, V value):
                返回值：V value
                    存储键值对时，Key 不重复，返回值 value 为 null
                    存储键值对时，Key 重复，使用新的 value 替换 map 中的 value
         */
        Map<String,String> map1 = new HashMap<>();

        //测试 Key
        String v1 = map1.put("hefery", "wahaha1");
        System.out.println("v1: " + v1);  //v1: null

        String v2 = map1.put("hefery", "wahaha2");
        System.out.println("v2: " + v2);  //v2: wahaha1

        System.out.println(map1);  //{hefery=wahaha2}

        //测试 value
        map1.put("张杰","谢娜");
        map1.put("李晨","范冰冰");
        map1.put("陈乔恩","范冰冰");

        System.out.println(map1);  //{陈乔恩=范冰冰, hefery=wahaha2, 李晨=范冰冰, 张杰=谢娜}
    }
}

/*
    Map 集合遍历：
        1.键找值
        2.键值对
 */
public class mapDemo {
    public static void main(String[] args) {
        /*Map<String,Integer> map = new HashMap<>();

        map.put("赵丽颖",168);
        map.put("林志玲",178);
        map.put("刘洋",188);

        //1.将所有 Key 取出，存入 Set 集合
        Set<String> set = map.keySet();

        //2.使用迭代器遍历
        Iterator<String> it = set.iterator();
        while (it.hasNext()){
            //3.通过 key 找到 value
            String key = it.next();
            Integer value = map.get(key);
            System.out.println(key + " = " + value);
        }

        //2.foreach遍历
        for (String key : set) {
            //3.通过 key 找到 value
            String value = it.next();
            System.out.println(key + " = " + value);
        }

        for (String key : map.keySet()) {
            String value = it.next();
            System.out.println(key + " = " + value);
        }*/

        System.out.println("===================================================");

        Map<String,Integer> map = new HashMap<>();

        map.put("赵丽颖",168);
        map.put("林志玲",178);
        map.put("刘洋",188);

        //1.使用 Map 集合中的 entrySet() 方法，把集合中的多个 Entry 对象取出，存入 Set 集合
        Set<Map.Entry<String,Integer>> set = map.entrySet();

        //2.迭代器遍历
        Iterator<Map.Entry<String, Integer>> it = set.iterator();
        while (it.hasNext()){
            Map.Entry<String, Integer> entry = it.next();
            //3.通过 getKey()、getValue() 得到 key、value 值
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " = " + value);
        }

        //foreach遍历
        for (Map.Entry<String, Integer> entry : set ) {
            //3.通过 getKey()、getValue() 得到 key、value 值
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " = " + value);
        }
    }
}

存储自定义类型的数据

@Data
public class Person{
    private String name;
    private int age;
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;

        if (age != person.age) return false;
        return name != null ? name.equals(person.name) : person.name == null;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

/*
    Map 集合包装 key 唯一：
        作为 key 元素，必须重写 hSHcODE() 和 equlas() 方法
        作为 value 值，可重复
 */
public class mapDemo {
    public static void main(String[] args) {
        show();
    }

    private static void show() {
        //创建 HashMap 集合
        HashMap<String,Person> map = new HashMap<>();
        HashMap<Person,String> map1 = new HashMap<>();

        //添加元素
        map.put("北京",new Person("张三",13));
        map.put("上海",new Person("李四",20));
        map.put("深圳",new Person("王五",10));
        map.put("北京",new Person("麻子",13));

        map1.put(new Person("张三",13),"北京");
        map1.put(new Person("李四",20),"上海");
        map1.put(new Person("王五",10),"深圳");
        map1.put(new Person("张三",13),"南京");

        //遍历
        Set<String> set = map.keySet();
        for (String key : set){
            Person value = map.get(key);
            System.out.println(key + " = " + value);
        }
        //麻子将张三替换

        //使用 entrySet() 和 foreach 遍历
        Set<Map.Entry<Person, String>> set1 = map1.entrySet();
        for (Map.Entry<Person, String> entry : set1) {
            Person key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key + " = " + value);
        }

    }
}

工作原理

HashMap 底层是 Hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry接口）实现，HashMap 通过 put & get 方法存储和获取

存储对象

将 Key/Value 键值传给 put() 方法：

1. 调用 hash(Key) 方法计算 Key 的 hashCode 值，然后结合数组长度，计算得数组下标
2. 调整数组大小（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）
   • 如果 Key 的 hashCode 值在 HashMap 中不存在，则执行插入，若存在，则发生碰撞
   • 如果 Key 的 hashCode 值在 HashMap 中存在，且它们两者 equals 返回 true，则更新 Value 值
   • 如果 Key 的 hashCode 值在 HashMap 中存在，且它们两者 equals 返回 false，则插入链表（JDK 1.7 之前头插法、JDK 1.8 尾插法）或者红黑树中（当碰撞导致链表大于 TREEIFY_THRESHOLD = 8 时，就把链表转换成红黑树）；如果集合中的键值对大于12，调用resize方法进行数组扩容

两个对象的 hashCode 相同会发生什么？

hashCode 相同，不一定就是相等的，两个对象所在数组的下标相同，"碰撞"就此发生

HashMap 使用链表存储对象，这个 Node 会存储到链表中

了解 hash 的实现吗？为什么要这样实现？

JDK 1.8 中，是通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞

异或运算符：保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞

HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？

table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30

loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容

扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）

如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命

获取对象

将 Key 传给 get() 方法

1. 调用 hash(Key) 方法（计算 Key 的 hash 值）从而获取该键值所在链表的数组下标
2. 顺序遍历链表，equals() 方法查找相同 Node 链表中 Key 值对应的 Value 值

hashCode 用于定位存储位置；equals用于定性的，比较两者是否相等

数组扩容

创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小

源码分析

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

    private static final long serialVersionUID = 362498820763181265L;
  
    /** 默认初识容量 */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // aka 16

    /** 最大容量 */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /** 加载因子 */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /** 当链表长度大于8，并且数组长度大于64，链表转化为红黑树 */
    static final int TREEIFY_THRESHOLD = 8;

    /** 当链表长度小于6，红黑树转化为链表 */
    static final int UNTREEIFY_THRESHOLD = 6;

    /** 转化为红黑树的最小数组长度 */
    static final int MIN_TREEIFY_CAPACITY = 64;

	/** 元素个数 */
    transient int size;
  
    /** 键值对 */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        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的数组 */
    transient Node<K,V>[] table;
  
    /** 无参构造 */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
  
  
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
  
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  
    /** HashMap刚创建时， table是nu11，为了节省空间，当添加第一个元素时， table容量调整为16 */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        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;
            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
                            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;
    }
  
    /** 当元素个数大于阈值（16*8.75=12）时，会进行扩容，扩容后大小为原来的2倍。目的是减少调整元素的个数 
        jdk1.8：当每个链表长度大于8，并且元素个数大于等于64时会调整为红黑树，目的提高执行效率
        当链表长度小于6时，调整成链表
        jdk1.8以前，链表头插入，jdk1.8以后链表尾插入*/
    final Node<K,V>[] resize() {
        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;
            }
            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"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        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);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
  
}

HashMap的底层数据结构

JDK1.8 之前底层是由 数组+链表 实现。JDK1.8之后底层是由 数组+链表 或 数组+红黑树 实现

数组中的每一个元素都是链表 Node，当链表长度超过 8 时，链表会转为红黑树

为什么在JDK1.8增加红黑树

红黑树：为了提高数据检索的速度。

对于数组和链表这种线性结构来说，当链表长度过长（数据有成百上千）的时候，会造成链表过深的问题，这种查找方式效率极低，时间复杂度是O(n)

红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢

红黑树特点：

• 每个节点非红即黑
• 根节点总是黑色的
• 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
• 每个叶子节点都是黑色的空节点（NIL节点）
• 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

不选择二叉查找树，是因为避免二叉查找树的缺陷：二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢

HashMap工作原理，put()和get()过程分别是怎么样

存储对象时，将 key 和 vaule 传给 put() 方法：

1. 判断数组是否为空
   • 为空进行初始化
   • 不为空，计算 key 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index
2. 查看 table[index] 是否存在数据
   • 没有数据就构造一个 Node 节点存放在 table[index] 中
   • 存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)
3. 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中
4. 如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于8并且数组长度大于64，大于的话链表转换为红黑树
5. 插入完成之后判断当前节点数是否大于阈值（capacity*loadFactor），如果大于开始扩容为原数组的二倍

获取对象时，将 key 传给 get() 方法：

1. 调用 hash(key) 方法获取 key 对应的 hash 值从而获取该键值对在数组中的下标
2. 对链表进行顺序遍历，使用 equals() 方法查找链表中相等的 key 对应的 value 值

数组是怎么扩容

创建一个新数组，新数组初始化容量大小是旧数组的两倍，对原数组中元素重新进行一次hash从而定位在新数组中的存储位置，元素在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小

为什么要对原数组中元素再重新进行一次hash？直接复制到新数组不行吗？
因为数组长度扩大后 Hash 规则也随之变化：Hash公式 —> index=HashCode(Key) & (Length - 1)

JDK8中对HashMap做了哪些改变

• 底层数据结构：JDK1.7中是数组+链表，JDK1.8中是数组+链表或数组+红黑树。JDK1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。（桶的数量必须大于64，小于64的时候只会扩容）
• 元素插入：JDK1.7 先判断是否需要扩容，再进行插入操作，发生哈希碰撞时，JDK7 会在链表的头部插入（头插法），JDK1.8 先插入插入完成之后再判断是否需要扩容，发生哈希碰撞时，会在链表的尾部插入（尾插法）
• 节点类型：JDK1.7 的 Entry 在 JDK1.8 中被 Node 替代
• 扩容方式：JDK1.7中需要对原数组中元素重新进行hash定位在新数组中的位置；JDK1.8中采用更简单的逻辑判断，原下标位置或原下标+旧数组的大小

JDK1.8之前使用头插法将Entry节点插入链表，头插法具体是怎么做？设计头插法目的？

目的：后来插入的值被查找的概率比较高，使用头插法可以提高查找的效率

为什么JDK1.8之后要改成尾插法？

JDK1.8之前扩容的时候，头插法会导致链表反转，在多线程情况下会出现环形链表，导致取值的时候出现死循环，JDK1.8开始在同样的前提下就不会导致死循环，因为在扩容转移前后链表的顺序不变，保持之前节点的引用关系

A线程和B线程同时向同一个下标位置插入节点，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环。

使用 new HashMap() 不传值，默认大小是 16，负载因子是 0.75。如果传入参数 Key，那么初始化容量大小为大于 Key 的 2 的最小整数幂。比如传入的是 10，那么初始化容量大小就是 16（2的4次方）

为什么HashMap的数组长度要取2的整数幂？

因为这样 数组长度-1 正好相当于一个“低位掩码”

“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问

以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111，和某散列值做“与”操作如下，结果就是截取了最低的四位值

HashMap中的哈希函数时怎么实现

key 的 hashcode 是一个 32 位的 int 类型值，hash 函数将 hashcode 的高 16 位和低 16位 进行异或运算

哈希函数为什么这么设计？
这是一个扰动函数，这样设计的原因主要有两点：

• 可以最大程度的降低 hash 碰撞的概率（hash值越分散越好）；
• 因为是高频操作，所以采用位运算，让算法更加高效

hashCode()和equals()区别

HashCode就像是一个签名，当两个对象的 Hashcode 一样的时候，两个对象就可能一样，但如果 Hashcode不一样，那么肯定不是同一个对象(相当于先确定一个大的范围，再用equals去比较)

hashcode可以减少equals比较的次数，提高运算效率。hashCode的存在主要是用于查找的捷性，如Hashtable，HashMap等

HashMap的内部节点是有序吗？有没有有序的Map？如何实现有序？

HashMap的内部节点无序，根据hash值随机插入

LinkedhashMap和TreeMap有序

• LinkedHashMap：LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before
  和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序
• TreeHashMap：
  TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较

HashMap线程安全吗？

不是，在多线程的情况下，JDK1.7 的 HashMap 会导致死循环、数据丢失、数据覆盖。在 JDK1.8 中如果有多个线程同时 put() 元素还是会存在数据覆盖的问题。以 JDK1.8 为例，A线程判断 index 位置为空后正好挂起，B线程也始向 index 位置写入节点数据，这时 A 线程恢复现场，执行赋值操作，就把 A 线程的数据给覆盖了

如何解决这个线程不安全的问题？并发下使用什么Map类？

可以使用线程安全的Map，如 ConcurrentHashMap

• HashTable 直接在操作方法上加 synchronized 关键字，锁住整个数组，粒度比较大
• Collections.synchronizedMap 使用 Collections 集合工具的内部类，通过传入 Map 封装出一个SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现
• ConcurrentHashMap 在 JDK1.7 中使用分段锁，降低了锁粒度，让并发度大大提高，在 JDK1.8 中直接采用了 CAS（无锁算法）+ synchronized 的方式来实现线程安全

ConcurrentHashMap 简单介绍

• 重要常量：private transient volatile int sizeCtl;

  当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容；
  当为 0 时，表示 table 还没有初始化；
  当为其他正数时，表示初始化或者下一次进行扩容的大小
  

• 数据结构：Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据
• 存储方法
  • 如果没有初始化，就调用 initTable() 方法来进行初始化
  • 如果没有 hash 冲突就直接 CAS 无锁插入
  • 如果需要扩容，就先进行扩容
  • 如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入
  • 如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一次进入循环
  • 如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容
• 获取方法:
• 扩容原理

HashMap，LinkedHashMap，TreeMap区别

• HashMap：在 Map 中插入、删除和定位元素
• TreeMap：实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）。按自然顺序或自定义顺序遍历键
• LinkedHashMap：保存了记录的插入顺序。输出的顺序和输入的顺序相同

HashMap和HashTable区别

• 线程安全：HashMap—线程不安全；HashTable—线程安全（导致 HashTable 效率比不上 HashMap）
• HashMap 中 key 和 value 都允许为 null。null 可以作为键，这样的键只有一个，可以有一个或多个 value 为 null。key 为 null 的键值对永远都放在以 table[0] 为头结点的链表中，允许多条记录的值为 null；HashTable在遇到 null 时，会抛出 NullPointerException 异常
• 默认初始化数组大小：HashMap 为 16，扩容 capacity*2；HashTable 为 11，扩容时 capacity*2+1
• HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode
• HashMap 继承自 AbstractMap 类；HashTable 继承与 Dictionary 类

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

Hashtable 的键值都不能为 null，所以可以用 get() 方法来判断是否含有某个键

HashMap & ConcurrentHashMap区别

除了加锁，原理上无太大区别。另外，HashMap 的键值对允许有null，但是ConCurrentHashMap 都不允许

为什么 ConcurrentHashMap 比 HashTable 效率要高？

HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；

ConcurrentHashMap

• JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
• JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry）。锁粒度降低了

ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

• 粒度降低
• 基于 JVM 的 synchronized 优化空间更大，更加自然
• 在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存

LinkedHashMap

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

1.底层：哈希表 + 链表
2.有序，存储取出元素顺序一致

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        HashMap<String,String> map = new HashMap<>();

        map.put("a","a");
        map.put("c","c");
        map.put("b","b");
        map.put("a","d");

        System.out.println(map); //key 值不允许重复，无序 {a=d, b=b, c=c}

        System.out.println("==========================================");

        LinkedHashMap<String,String> linked = new LinkedHashMap<>();
        linked.put("a","a");
        linked.put("c","c");
        linked.put("b","b");
        linked.put("a","d");

        System.out.println(linked); //key 值不允许重复，有序 {a=d, c=c, b=b}
    }
}

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
        map.put("邓超", "孙俪");
        map.put("李晨", "范冰冰");
        map.put("刘德华", "朱丽倩");
        Set<Entry<String, String>> entrySet = map.entrySet();
        for (Entry<String, String> entry : entrySet) {
            System.out.println(entry.getKey() + "  " + entry.getValue());
        }
    }
}

ConcurrentHashMap<K,V>

所有操作都是线程安全的，但获取操作不必锁定，并且不支持以某种防止所有访问的方式锁定整个表
此类可以通过程序完全与 Hashtable 进行互操作，这取决于其线程安全，而与其同步细节无关

构造函数

重要方法