作为一位小菜 ”一面面试官“，面试过程中，我必定会问 Java 汇合的内容，同时作为求职者，也必定会被问到汇合，所以整顿下 Java 汇合面试题

说说常见的汇合有哪些吧？

HashMap说一下，其中的Key须要重写hashCode()和equals()吗？

HashMap中key和value能够为null吗？容许几个为null呀？

HashMap线程平安吗?ConcurrentHashMap和hashTable有什么区别？

List和Set说一下，当初有一个ArrayList，对其中的所有元素依照某一属性大小排序，应该怎么做？

ArrayList 和 Vector 的区别

list 能够删除吗，遍历的时候能够删除吗，为什么

面向对象语言对事物的体现都是以对象的模式，所以为了不便对多个对象的操作，须要将对象进行存储，汇合就是存储对象最罕用的一种形式，也叫容器。

从下面的汇合框架图能够看到，Java 汇合框架次要包含两种类型的容器

  • 一种是汇合（Collection），存储一个元素汇合
  • 另一种是图（Map），存储键/值对映射。

Collection 接口又有 3 种子类型，List、Set 和 Queue，再上面是一些抽象类，最初是具体实现类，罕用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

汇合框架是一个用来代表和操纵汇合的对立架构。所有的汇合框架都蕴含如下内容：

  • 接口：是代表汇合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的形式操作汇合对象
  • 实现（类）：是汇合接口的具体实现。从实质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
  • 算法：是实现汇合接口的对象里的办法执行的一些有用的计算，例如：搜寻和排序。这些算法被称为多态，那是因为雷同的办法能够在类似的接口上有着不同的实现。

说说罕用的汇合有哪些吧？

Map 接口和 Collection 接口是所有汇合框架的父接口：

  1. Collection接口的子接口包含：Set、List、Queue
  2. List是有序的容许有反复元素的 Collection，实现类次要有：ArrayList、LinkedList、Stack以及Vector等
  3. Set是一种不蕴含反复元素且无序的Collection，实现类次要有：HashSet、TreeSet、LinkedHashSet等
  4. Map没有继承Collection接口，Map提供key到value的映射。实现类次要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等

ArrayList 和 Vector 的区别

相同点：

  • ArrayList 和 Vector 都是继承了雷同的父类和实现了雷同的接口（都实现了List，有序、容许反复和null）

    extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • 底层都是数组（Object[]）实现的
  • 初始默认长度都为10

不同点：

  • 同步性：Vector 中的 public 办法少数增加了 synchronized 关键字、以确保办法同步、也即是 Vector 线程平安、ArrayList 线程不平安
  • 性能：Vector 存在 synchronized 的锁期待状况、须要期待开释锁这个过程、所以性能绝对较差

  • 扩容大小：ArrayList在底层数组不够用时在原来的根底上扩大 0.5 倍，Vector默认是扩大 1 倍

    扩容机制，扩容办法其实就是新创建一个数组，而后将旧数组的元素都复制到新数组外面。其底层的扩容办法都在 grow() 中（基于JDK8）

    • ArrayList 的 grow()，在满足扩容条件时、ArrayList以1.5 倍的形式在扩容（oldCapacity >> 1 ，右移运算，相当于除以 2，后果为二分之一的 oldCapacity）

      private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    //newCapacity = oldCapacity + O.5*oldCapacity,此处扩容0.5倍    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);}

    • Vector 的 grow()，Vector 比 ArrayList多一个属性，扩大因子capacityIncrement，能够扩容大小。当扩容容量增量大于0时、新数组长度为原数组长度+扩容容量增量、否则新数组长度为原数组长度的2倍

      private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    //    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?                                     capacityIncrement : oldCapacity);    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    elementData = Arrays.copyOf(elementData, newCapacity);}

ArrayList 与 LinkedList 区别

  • 是否保障线程平安： ArrayList 和 LinkedList 都是不同步的，也就是不保障线程平安；
  • 底层数据结构： Arraylist 底层应用的是 Object 数组；LinkedList 底层应用的是双向循环链表数据结构；

  • 插入和删除是否受元素地位的影响：

    • ArrayList 采纳数组存储，所以插入和删除元素的工夫复杂度受元素地位的影响。 比方：执行 add(E e)办法的时候， ArrayList 会默认在将指定的元素追加到此列表的开端，这种状况工夫复杂度就是O(1)。然而如果要在指定地位 i 插入和删除元素的话（ add(intindex,E element)）工夫复杂度就为 O(n-i)。因为在进行上述操作的时候汇合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
    • LinkedList 采纳链表存储，所以插入，删除元素工夫复杂度不受元素地位的影响，都是近似 $O(1)$，而数组为近似 $O(n)$。
    • ArrayList 个别利用于查问较多但插入以及删除较少状况，如果插入以及删除较多则倡议应用 LinkedList
  • 是否反对疾速随机拜访： LinkedList 不反对高效的随机元素拜访，而 ArrayList 实现了 RandomAccess 接口，所以有随机拜访性能。疾速随机拜访就是通过元素的序号疾速获取元素对象(对应于 get(intindex)办法)。
  • 内存空间占用： ArrayList 的空间节约次要体现在在 list 列表的结尾会预留肯定的容量空间，而 LinkedList 的空间破费则体现在它的每一个元素都须要耗费比 ArrayList 更多的空间（因为要寄存间接后继和间接前驱以及数据）。

高级工程师的我，可不得看看源码，具体分析下：

  • ArrayList工作原理其实很简略，底层是动静数组，每次创立一个 ArrayList 实例时会调配一个初始容量（没有指定初始容量的话，默认是 10），以add办法为例，如果没有指定初始容量，当执行add办法，先判断以后数组是否为空，如果为空则给保留对象的数组调配一个最小容量，默认为10。当增加大容量元素时，会先减少数组的大小，以进步增加的效率；
  • LinkedList 是有序并且反对元素反复的汇合，底层是基于双向链表的，即每个节点既蕴含指向其后继的援用也包含指向其前驱的援用。链表无容量限度，但双向链表自身应用了更多空间，也须要额定的链表指针操作。按下标拜访元素 get(i)/set(i,e) 要喜剧的遍历链表将指针挪动到位(如果i>数组大小的一半，会从开端移起)。插入、删除元素时批改前后节点的指针即可，但还是要遍历局部链表的指针能力挪动到下标所指的地位，只有在链表中间的操作add()， addFirst()，removeLast()或用 iterator() 上的 remove() 能省掉指针的挪动。此外 LinkedList 还实现了 Deque（继承自Queue接口）接口，能够当做队列应用。

不会囊括所有办法，只是为了学习，记录思维。

ArrayList 和 LinkedList 两者都实现了 List 接口

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

结构器

ArrayList 提供了 3 个结构器，①无参结构器 ②带初始容量结构器 ③参数为汇合结构器

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{   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 ArrayList(Collection<? extends E> c) { //...}       }

LinkedList 提供了 2 个结构器，因为基于链表，所以也就没有初始化大小，也没有扩容的机制，就是始终在后面或者前面插插插~~

public LinkedList() {}public LinkedList(Collection<? extends E> c) {    this();    addAll(c);}// 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;    }}

插入

ArrayList:

public boolean add(E e) {    // 确保数组的容量，保障能够增加该元素    ensureCapacityInternal(size + 1);  // Increments modCount!!    // 将该元素放入数组中    elementData[size++] = e;    return true;}private void ensureCapacityInternal(int minCapacity) {    // 如果数组是空的，那么会初始化该数组    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        // DEFAULT_CAPACITY 为 10,所以调用无参默认 ArrayList 构造方法初始化的话，默认的数组容量为 10        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // 确保数组的容量，如果不够的话，调用 grow 办法扩容    if (minCapacity - elementData.length > 0)        grow(minCapacity);}//扩容具体的办法private void grow(int minCapacity) {    // 以后数组的容量    int oldCapacity = elementData.length;    // 新数组扩容为原来容量的 1.5 倍    int newCapacity = oldCapacity + (oldCapacity >> 1);    // 如果新数组扩容容量还是比起码须要的容量还要小的话，就设置裁减容量为最小须要的容量    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    //判断新数组容量是否曾经超出最大数组范畴，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8    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);}

当然也能够插入指定地位，还有一个重载的办法 add(int index, E element)

public void add(int index, E element) {    // 判断 index 有没有超出索引的范畴    rangeCheckForAdd(index);    // 和之前的操作是一样的，都是保障数组的容量足够    ensureCapacityInternal(size + 1);  // Increments modCount!!    // 将指定地位及其前面数据向后挪动一位    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);    // 将该元素增加到指定的数组地位    elementData[index] = element;    // ArrayList 的大小扭转    size++;}

能够看到每次插入指定地位都要挪动元素，效率较低。

再来看 LinkedList 的插入，也有插入开端，插入指定地位两种，因为基于链表，必定得先有个 Node

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;    }}
public boolean add(E e) {    // 间接往队尾加元素    linkLast(e);    return true;}void linkLast(E e) {    // 保留原来链表尾部节点，last 是全局变量，用来示意队尾元素    final Node<E> l = last;    // 为该元素 e 新建一个节点    final Node<E> newNode = new Node<>(l, e, null);    // 将新节点设为队尾    last = newNode;    // 如果原来的队尾元素为空，那么阐明原来的整个列表是空的，就把新节点赋值给头结点    if (l == null)        first = newNode;    else    // 原来尾结点的前面为新生成的结点        l.next = newNode;    // 节点数 +1    size++;    modCount++;}public void add(int index, E element) {    // 查看 index 有没有超出索引范畴    checkPositionIndex(index);    // 如果追加到尾部，那么就跟 add(E e) 一样了    if (index == size)        linkLast(element);    else    // 否则就是插在其余地位     linkBefore(element, node(index));}//linkBefore办法中调用了这个node办法，相似二分查找的优化Node<E> node(int index) {    // assert isElementIndex(index);    // 如果 index 在前半段，从前往后遍历获取 node    if (index < (size >> 1)) {        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        // 如果 index 在后半段，从后往前遍历获取 node        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}void linkBefore(E e, Node<E> succ) {    // assert succ != null;    // 保留 index 节点的前节点    final Node<E> pred = succ.prev;    // 新建一个指标节点    final Node<E> newNode = new Node<>(pred, e, succ);    succ.prev = newNode;    // 如果是在结尾处插入的话    if (pred == null)        first = newNode;    else        pred.next = newNode;    size++;    modCount++;}

获取

ArrayList 的 get() 办法很简略，就是在数组中返回指定地位的元素即可，所以效率很高

public E get(int index) {    // 查看 index 有没有超出索引的范畴    rangeCheck(index);    // 返回指定地位的元素    return elementData(index);}

LinkedList 的 get() 办法，就是在外部调用了上边看到的 node() 办法，判断在前半段还是在后半段，而后遍历失去即可。

public E get(int index) {    checkElementIndex(index);    return node(index).item;}

HashMap的底层实现

什么时候会应用HashMap？他有什么特点？

你晓得HashMap的工作原理吗？

你晓得get和put的原理吗？equals()和hashCode()的都有什么作用？

你晓得hash的实现吗？为什么要这样实现？

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

HashMap 在 JDK 7 和 JDK8 中的实现形式略有不同。离开记录。

深刻 HahsMap 之前，先要理解的概念

  1. initialCapacity：初始容量。指的是 HashMap 汇合初始化的时候本身的容量。能够在构造方法中指定；如果不指定的话，总容量默认值是 16 。须要留神的是初始容量必须是 2 的幂次方。（1.7中，已知HashMap中将要寄存的KV个数的时候，设置一个正当的初始化容量能够无效的进步性能）

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  2. size：以后 HashMap 中曾经存储着的键值对数量，即 HashMap.size() 。
  3. loadFactor：加载因子。所谓的加载因子就是 HashMap (以后的容量/总容量) 达到肯定值的时候，HashMap 会施行扩容。加载因子也能够通过构造方法中指定，默认的值是 0.75 。举个例子，假如有一个 HashMap 的初始容量为 16 ，那么扩容的阀值就是 0.75 * 16 = 12 。也就是说，在你打算存入第 13 个值的时候，HashMap 会先执行扩容。
  4. threshold：扩容阀值。即 扩容阀值 = HashMap 总容量 * 加载因子。以后 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为以后 HashMap 总容量的两倍。比方，以后 HashMap 的总容量为 16 ，那么扩容之后为 32 。
  5. table：Entry 数组。咱们都晓得 HashMap 外部存储 key/value 是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。

JDK1.7 实现

JDK1.7 中 HashMap 由 数组+链表 组成（“链表散列” 即数组和链表的结合体），数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的（HashMap 采纳 “拉链法也就是链地址法” 解决抵触），如果定位到的数组地位不含链表（以后 entry 的 next 指向 null ），那么对于查找，增加等操作很快，仅需一次寻址即可；如果定位到的数组蕴含链表，对于增加操作，其工夫复杂度仍然为 O(1)，因为最新的 Entry 会插入链表头部，即须要简略扭转援用链即可，而对于查找操作来讲，此时就须要遍历链表，而后通过 key 对象的 equals 办法逐个比对查找。

所谓 “拉链法” 就是将链表和数组相结合。也就是说创立一个链表数组，数组中每一格就是一个链表。若遇到哈希抵触，则将抵触的值加到链表中即可。

源码解析

构造方法

《阿里巴巴 Java 开发手册》举荐汇合初始化时，指定汇合初始值大小。（阐明：HashMap 应用HashMap(int initialCapacity) 初始化）倡议起因： https://www.zhihu.com/question/314006228/answer/611170521

// 默认的构造方法应用的都是默认的初始容量和加载因子// DEFAULT_INITIAL_CAPACITY = 16，DEFAULT_LOAD_FACTOR = 0.75fpublic HashMap() {    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}// 能够指定初始容量，并且应用默认的加载因子public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}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;    threshold = initialCapacity;    // 空办法    init();}public HashMap(Map<? extends K, ? extends V> m) {  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,                DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  inflateTable(threshold);  putAllForCreate(m);}

HashMap 的前 3 个构造方法最初都会去调用 HashMap(int initialCapacity, float loadFactor) 。在其外部去设置初始容量和加载因子。而最初的 init() 是空办法，次要给子类实现，比方LinkedHashMap。

put() 办法
public V put(K key, V value) {    // 如果 table 数组为空时先创立数组，并且设置扩容阀值    if (table == EMPTY_TABLE) {        inflateTable(threshold);    }    // 如果 key 为空时，调用 putForNullKey 办法非凡解决    if (key == null)        return putForNullKey(value);    // 计算 key 的哈希值    int hash = hash(key);    // 依据计算出来的哈希值和以后数组的长度计算在数组中的索引    int i = indexFor(hash, table.length);    // 先遍历该数组索引下的整条链表    // 如果该 key 之前曾经在 HashMap 中存储了的话，间接替换对应的 value 值即可    for (Entry<K,V> e = table[i]; e != null; e = e.next) {        Object k;       //先判断hash值是否一样，如果一样，再判断key是否一样，不同对象的hash值可能一样        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {            V oldValue = e.value;            e.value = value;            e.recordAccess(this);            return oldValue;        }    }    modCount++;    // 如果该 key 之前没有被存储过，那么就进入 addEntry 办法    addEntry(hash, key, value, i);    return null;}void addEntry(int hash, K key, V value, int bucketIndex) {    // 以后容量大于或等于扩容阀值的时候，会执行扩容    if ((size >= threshold) && (null != table[bucketIndex])) {        // 扩容为原来容量的两倍        resize(2 * table.length);        // 从新计算哈希值        hash = (null != key) ? hash(key) : 0;        // 重新得到在新数组中的索引        bucketIndex = indexFor(hash, table.length);    }    // 创立节点    createEntry(hash, key, value, bucketIndex);}//扩容，创立了一个新的数组，而后把数据全副复制过来，再把新数组的援用赋给 tablevoid resize(int newCapacity) {    Entry[] oldTable = table;  //援用扩容前的Entry数组    int oldCapacity = oldTable.length;    if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果曾经达到最大(2^30)了        threshold = Integer.MAX_VALUE;  //批改阈值为int的最大值(2^31-1)，这样当前就不会扩容了        return;    }    // 创立新的 entry 数组    Entry[] newTable = new Entry[newCapacity];    // 将旧 entry 数组中的数据复制到新 entry 数组中    transfer(newTable, initHashSeedAsNeeded(newCapacity));    // 将新数组的援用赋给 table    table = newTable;    // 计算新的扩容阀值    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}void transfer(Entry[] newTable) {     Entry[] src = table;                   //src援用了旧的Entry数组     int newCapacity = newTable.length;     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组         Entry<K,V> e = src[j];             //获得旧Entry数组的每个元素         if (e != null) {             src[j] = null;//开释旧Entry数组的对象援用（for循环后，旧的Entry数组不再援用任何对象）             do {                 Entry<K,V> next = e.next;                 int i = indexFor(e.hash, newCapacity); //！！从新计算每个元素在数组中的地位                 e.next = newTable[i]; //标记[1]                 newTable[i] = e;      //将元素放在数组上                 e = next;             //拜访下一个Entry链上的元素             } while (e != null);         }     }} void createEntry(int hash, K key, V value, int bucketIndex) {   // 取出table中下标为bucketIndex的Entry    Entry<K,V> e = table[bucketIndex];   // 利用key、value来构建新的Entry   // 并且之前寄存在table[bucketIndex]处的Entry作为新Entry的next   // 把新创建的Entry放到table[bucketIndex]地位    table[bucketIndex] = new Entry<>(hash, key, value, e);    // 以后 HashMap 的容量加 1    size++;}

最初的 createEntry() 办法就阐明了当 hash 抵触时，采纳的拉链法来解决 hash 抵触的，并且是把新元素插入到单链表的表头。

get() 办法
public V get(Object key) {    // 如果 key 是空的，就调用 getForNullKey 办法非凡解决    if (key == null)        return getForNullKey();    // 获取 key 绝对应的 entry     Entry<K,V> entry = getEntry(key);    return null == entry ? null : entry.getValue();}//找到对应 key 的数组索引，而后遍历链表查找即可final Entry<K,V> getEntry(Object key) {    if (size == 0) {        return null;    }    // 计算 key 的哈希值    int hash = (key == null) ? 0 : hash(key);    // 失去数组的索引，而后遍历链表，查看是否有雷同 key 的 Entry    for (Entry<K,V> e = table[indexFor(hash, table.length)];         e != null;         e = e.next) {        Object k;        if (e.hash == hash &&            ((k = e.key) == key || (key != null && key.equals(k))))            return e;    }    // 没有的话，返回 null    return null;}

JDK1.8 实现

JDK 1.7 中，如果哈希碰撞过多，拉链过长，极其状况下，所有值都落入了同一个桶内，这就进化成了一个链表。通过 key 值查找要遍历链表，效率较低。 JDK1.8 在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以缩小搜寻工夫。

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺点，因为二叉查找树在某些状况下会进化成一个线性构造。

源码解析

构造方法

JDK8 构造方法改变不是很大

public HashMap() {  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(int initialCapacity) {  this(initialCapacity, DEFAULT_LOAD_FACTOR);}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);}public HashMap(Map<? extends K, ? extends V> m) {  this.loadFactor = DEFAULT_LOAD_FACTOR;  putMapEntries(m, false);}
确定哈希桶数组索引地位（hash 函数的实现）
//办法一：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);}//办法二：static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有提取这个办法，而是放在了其余办法中，比方 put 的p = tab[i = (n - 1) & hash] return h & (length-1); //第三步 取模运算}

HashMap 定位数组索引地位，间接决定了 hash 办法的离散性能。Hash 算法实质上就是三步：取key的hashCode值、高位运算、取模运算。

为什么要这样呢？

HashMap 的长度为什么是 2 的幂次方?

目标当然是为了缩小哈希碰撞，使 table 里的数据分布的更平均。

  1. HashMap 中桶数组的大小 length 总是2的幂，此时，h & (table.length -1) 等价于对 length 取模 h%length。但取模的计算效率没有位运算高，所以这是是一个优化。假如 h = 185，table.length-1 = 15(0x1111)，其实散列真正失效的只是低 4bit 的无效位，所以很容易碰撞。

  2. 图中的 hash 是由键的 hashCode 产生。计算余数时，因为 n 比拟小，hash 只有低4位参加了计算，高位的计算能够认为是有效的。这样导致了计算结果只与低位信息无关，高位数据没发挥作用。为了解决这个缺点，咱们能够上图中的 hash 高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4)。通过这种形式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参加到计算中。此时的计算过程如下：

    在 Java 中，hashCode 办法产生的 hash 是 int 类型，32 位宽。前16位为高位，后16位为低位，所以要右移16位，即 hash ^ (hash >>> 16) 。这样还减少了hash 的复杂度，进而影响 hash 的散布性。

HashMap 的长度为什么是2的幂次方？

为了能让HashMap存取高效，尽量减少碰撞，也就是要尽量把数据调配平均，Hash值的范畴是-2147483648到2147483647，前后加起来有40亿的映射空间，只有哈希函数映射的比拟平均涣散，个别利用是很难呈现碰撞的，但一个问题是40亿的数组内存是放不下的。所以这个散列值是不能间接拿来用的。用之前须要先对数组长度取模运算，失去余数能力用来寄存地位也就是对应的数组小标。这个数组下标的计算方法是 (n-1)&hash，n代表数组长度。

这个算法应该如何设计呢？

咱们首先可能会想到采纳%取余的操作来实现。然而，重点来了。

取余操作中如果除数是2的幂次则等价于其除数减一的与操作，也就是说 hash%length=hash&(length-1)，但前提是 length 是 2 的 n 次方，并且采纳 &运算比 %运算效率高，这也就解释了 HashMap 的长度为什么是2的幂次方。

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) {      // 如果 first 是 TreeNode 类型，则调用黑红树查找办法      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;}
put() 办法

public V put(K key, V value) {  // 对key的hashCode()做hash  return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {  Node<K,V>[] tab; Node<K,V> p; int n, i;  // tab为空则创立  if ((tab = table) == null || (n = tab.length) == 0)    n = (tab = resize()).length;  // 计算index，并对null做解决  if ((p = tab[i = (n - 1) & hash]) == null)    tab[i] = newNode(hash, key, value, null);  else {    Node<K,V> e; K k;    // 节点key存在，间接笼罩value    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);          //链表长度大于8转换为红黑树进行解决          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st            treeifyBin(tab, hash);          break;        }        //key曾经存在间接笼罩value        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;}
HashMap 的 put 办法的具体流程？

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.依据键值key计算hash值得到插入的数组索引i，如果table[i]==null，间接新建节点增加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果雷同间接笼罩value，否则转向④，这里的雷同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key曾经存在间接笼罩value即可；

⑥.插入胜利后，判断理论存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

resize() 扩容
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) {      //批改阈值为int的最大值(2^31-1)，这样当前就不会扩容了      threshold = Integer.MAX_VALUE;      return oldTab;    }     // 没超过最大值，就裁减为原来的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);  }  // 计算新的resize下限  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;  // 把每个bucket都挪动到新的buckets中  if (oldTab != null) {    //  循环遍历旧的 table 数组    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);         //  遍历链表，将原链表节点分成lo和hi两个链表         // 其中 lo 示意在原来的桶地位，hi 示意在新的桶地位        else { // preserve order  链表优化重hash的代码块          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;            }            // 原索引+oldCap            else {              if (hiTail == null)                hiHead = e;              else                hiTail.next = e;              hiTail = e;            }          } while ((e = next) != null);          // 原索引放到bucket里          if (loTail != null) {            loTail.next = null;            newTab[j] = loHead;          }          // 原索引+oldCap放到bucket里          if (hiTail != null) {            hiTail.next = null;            newTab[j + oldCap] = hiHead;          }        }      }    }  }  return newTab;}
HashMap的扩容操作是怎么实现的？
  1. 在jdk1.8中，resize办法是在HashMap中的键值对大于阀值时或者初始化时，就调用resize办法进行扩容；
  2. 每次扩大的时候，都是扩大2倍；
  3. 扩大后Node对象的地位要么在原地位，要么挪动到原偏移量两倍的地位。

在 putVal() 中，咱们看到在这个函数外面应用到了2次 resize() 办法，resize() 办法示意在进行第一次初始化时会对其进行扩容，或者当该数组的理论大小大于其扩容阈值（第一次为0.75 * 16 = 12），这个时候在扩容的同时也会随同的桶下面的元素进行从新散发，这也是JDK1.8版本的一个优化的中央，在1.7中，扩容之后须要从新去计算其Hash值，依据Hash值对其进行散发，但在1.8 版本中，则是依据在同一个桶的地位中进行判断(e.hash & oldCap)是否为0，从新进行hash调配后，该元素的地位要么停留在原始地位，要么挪动到原始地位+减少的数组大小这个地位上

链表树化

当桶中链表长度超过 TREEIFY_THRESHOLD（默认为8）时，就会调用 treeifyBin 办法进行树化操作。但此时并不一定会树化，因为在 treeifyBin 办法中还会判断 HashMap 的容量是否大于等于 64。如果容量大于等于 64，那么进行树化，否则优先进行扩容。

为什么树化还要判断整体容量是否大于 64 呢？

当桶数组容量比拟小时，键值对节点 hash 的碰撞率可能会比拟高，进而导致链表长度较长，从而导致查问效率低下。这时候咱们有两种抉择，一种是扩容，让哈希碰撞率低一些。另一种是树化，进步查问效率。

如果咱们采纳扩容，那么咱们须要做的就是做一次链表数据的复制。而如果咱们采纳树化，那么咱们须要将链表转化成红黑树。到这里，貌似没有什么太大的区别，但咱们让场景持续延长上来。当插入的数据越来越多，咱们会发现须要转化成树的链表越来越多。

到了肯定容量，咱们就须要进行扩容了。这个时候咱们有许多树化的红黑树，在扩容之时，咱们须要将许多的红黑树拆分成链表，这是一个挺大的老本。而如果咱们在容量小的时候就进行扩容，那么须要树化的链表就越少，咱们扩容的老本也就越低。

接下来咱们看看链表树化是怎么做的：

final void treeifyBin(Node<K,V>[] tab, int hash) {    int n, index; Node<K,V> e;    // 1. 容量小于 MIN_TREEIFY_CAPACITY，优先扩容    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)        resize();    // 2. 桶不为空，那么进行树化操作    else if ((e = tab[index = (n - 1) & hash]) != null) {        TreeNode<K,V> hd = null, tl = null;        // 2.1 先将链表转成 TreeNode 示意的双向链表        do {            TreeNode<K,V> p = replacementTreeNode(e, null);            if (tl == null)                hd = p;            else {                p.prev = tl;                tl.next = p;            }            tl = p;        } while ((e = e.next) != null);        // 2.2 将 TreeNode 示意的双向链表树化        if ((tab[index] = hd) != null)            hd.treeify(tab);    }}

咱们能够看到链表树化的整体思路也比拟清晰。首先将链表转成 TreeNode 示意的双向链表，之后再调用 treeify() 办法进行树化操作。那么咱们持续看看 treeify() 办法的实现。

final void treeify(Node<K,V>[] tab) {    TreeNode<K,V> root = null;    // 1. 遍历双向 TreeNode 链表，将 TreeNode 节点一个个插入    for (TreeNode<K,V> x = this, next; x != null; x = next) {        next = (TreeNode<K,V>)x.next;        x.left = x.right = null;        // 2. 如果 root 节点为空，那么间接将 x 节点设置为根节点        if (root == null) {            x.parent = null;            x.red = false;            root = x;        }        else {            K k = x.key;            int h = x.hash;            Class<?> kc = null;                        // 3. 如果 root 节点不为空，那么进行比拟并在适合的中央插入            for (TreeNode<K,V> p = root;;) {                int dir, ph;                K pk = p.key;                // 4. 计算 dir 值，-1 示意要从左子树查找插入点，1示意从右子树                if ((ph = p.hash) > h)                    dir = -1;                else if (ph < h)                    dir = 1;                else if ((kc == null &&                          (kc = comparableClassFor(k)) == null) ||                         (dir = compareComparables(kc, k, pk)) == 0)                    dir = tieBreakOrder(k, pk);                TreeNode<K,V> xp = p;                // 5. 如果查找到一个 p 点，这个点是叶子节点                // 那么这个就是插入地位                if ((p = (dir <= 0) ? p.left : p.right) == null) {                    x.parent = xp;                       if (dir <= 0)                        xp.left = x;                    else                        xp.right = x;                    // 做插入后的动平衡                    root = balanceInsertion(root, x);                    break;                }            }        }    }    // 6.将 root 节点挪动到链表头    moveRootToFront(tab, root);}

从下面代码能够看到，treeify() 办法其实就是将双向 TreeNode 链表进一步树化成红黑树。其中大抵的步骤为：

  • 遍历 TreeNode 双向链表，将 TreeNode 节点一个个插入
  • 如果 root 节点为空，那么示意红黑树当初为空，间接将该节点作为根节点。否则须要查找到适合的地位去插入 TreeNode 节点。
  • 通过比拟与 root 节点的地位，一直寻找最合适的点。如果最终该节点的叶子节点为空，那么该节点 p 就是插入节点的父节点。接着，将 x 节点的 parent 援用指向 xp 节点，xp 节点的左子节点或右子节点指向 x 节点。
  • 接着，调用 balanceInsertion 做一次动态平衡。
  • 最初，调用 moveRootToFront 办法将 root 节点挪动到链表头。

对于 balanceInsertion() 动平衡能够参考红黑树的插入动平衡，这里暂不深刻解说。最初咱们持续看看 moveRootToFront 办法。

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {    int n;    if (root != null && tab != null && (n = tab.length) > 0) {        int index = (n - 1) & root.hash;        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];        // 如果插入红黑树的 root 节点不是链表的第一个元素        // 那么将 root 节点取出来，插在 first 节点后面        if (root != first) {            Node<K,V> rn;            tab[index] = root;            TreeNode<K,V> rp = root.prev;            // 上面的两个 if 语句，做的事件是将 root 节点取出来            // 让 root 节点的前继指向其后继节点            // 让 root 节点的后继指向其前继节点            if ((rn = root.next) != null)                ((TreeNode<K,V>)rn).prev = rp;            if (rp != null)                rp.next = rn;            // 这里间接让 root 节点插入到 first 节点后方            if (first != null)                first.prev = root;            root.next = first;            root.prev = null;        }        assert checkInvariants(root);    }}
红黑树拆分

扩容后，一般节点须要从新映射，红黑树节点也不例外。依照个别的思路，咱们能够先把红黑树转成链表，之后再从新映射链表即可。但因为红黑树插入的时候，TreeNode 保留了元素插入的程序，所以间接能够依照插入程序还原成链表。这样就防止了将红黑树转成链表后再进行哈希映射，无形中进步了效率。

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {    TreeNode<K,V> b = this;    // Relink into lo and hi lists, preserving order    TreeNode<K,V> loHead = null, loTail = null;    TreeNode<K,V> hiHead = null, hiTail = null;    int lc = 0, hc = 0;    // 1. 将红黑树当成是一个 TreeNode 组成的双向链表    // 依照链表扩容一样，别离放入 loHead 和 hiHead 结尾的链表中    for (TreeNode<K,V> e = b, next; e != null; e = next) {        next = (TreeNode<K,V>)e.next;        e.next = null;        // 1.1. 扩容后的地位不变，还是原来的地位，该节点放入 loHead 链表        if ((e.hash & bit) == 0) {            if ((e.prev = loTail) == null)                loHead = e;            else                loTail.next = e;            loTail = e;            ++lc;        }        // 1.2 扩容后的地位扭转了，放入 hiHead 链表        else {            if ((e.prev = hiTail) == null)                hiHead = e;            else                hiTail.next = e;            hiTail = e;            ++hc;        }    }    // 2. 对 loHead 和 hiHead 进行树化或链表化    if (loHead != null) {        // 2.1 如果链表长度小于阈值，那就链表化，否则树化        if (lc <= UNTREEIFY_THRESHOLD)            tab[index] = loHead.untreeify(map);        else {            tab[index] = loHead;            if (hiHead != null) // (else is already treeified)                loHead.treeify(tab);        }    }    if (hiHead != null) {        if (hc <= UNTREEIFY_THRESHOLD)            tab[index + bit] = hiHead.untreeify(map);        else {            tab[index + bit] = hiHead;            if (loHead != null)                hiHead.treeify(tab);        }    }}

从下面的代码咱们晓得红黑树的扩容也和链表的转移是一样的，不同的是其转化成 hiHead 和 loHead 之后，会依据链表长度抉择拆分成链表还是继承维持红黑树的构造。

红黑树链化

咱们在说到红黑树拆分的时候说到，红黑树结构在扩容的时候如果长度低于阈值，那么就会将其转化成链表。其实现代码如下：

final Node<K,V> untreeify(HashMap<K,V> map) {    Node<K,V> hd = null, tl = null;    for (Node<K,V> q = this; q != null; q = q.next) {        Node<K,V> p = map.replacementNode(q, null);        if (tl == null)            hd = p;        else            tl.next = p;        tl = p;    }    return hd;}

因为红黑树中蕴含了插入元素的程序，所以当咱们将红黑树拆分成两个链表 hiHead 和 loHead 时，其还是放弃着原来的程序的。所以此时咱们只须要循环遍历一遍，而后将 TreeNode 节点换成 Node 节点即可。

HashMap 为什么线程不平安

  1. put的时候导致的多线程数据不统一。
    这个问题比拟好设想，比方有两个线程A和B，首先A心愿插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，而后获取到该桶外面的链表头结点，此时线程A的工夫片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B胜利将记录插到了桶外面，假如线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B胜利插入之后，线程A再次被调度运行时，它仍然持有过期的链表头然而它对此无所不知，以至于它认为它应该这样做，如此一来就笼罩了线程B插入的记录，这样线程B插入的记录就凭空隐没了，造成了数据不统一的行为。

  2. 另外一个比拟显著的线程不平安的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%），具体分析如下：

    上面的代码是resize的核心内容：

void transfer(Entry[] newTable, boolean rehash) {          int newCapacity = newTable.length;          for (Entry<K,V> e : table) {                while(null != e) {                  Entry<K,V> next = e.next;                           if (rehash) {                      e.hash = null == e.key ? 0 : hash(e.key);                  }                  int i = indexFor(e.hash, newCapacity);                   e.next = newTable[i];                  newTable[i] = e;                  e = next;              }         }      }

这个办法的性能是将原来的记录从新计算在新桶的地位，而后迁徙过来。

多线程HashMap的resize

咱们假如有两个线程同时须要执行resize操作，咱们原来的桶数量为2，记录数为3，须要resize桶到4，原来的记录别离为：[3,A],[7,B],[5,C]，在原来的map外面，咱们发现这三个entry都落到了第二个桶外面。
假如线程thread1执行到了transfer办法的Entry next = e.next这一句，而后工夫片用完了，此时的e = [3,A], next = [7,B]。线程thread2被调度执行并且顺利完成了resize操作，须要留神的是，此时的[7,B]的next为[3,A]。此时线程thread1从新被调度运行，此时的thread1持有的援用是曾经被thread2 resize之后的后果。线程thread1首先将[3,A]迁徙到新的数组上，而后再解决[7,B]，而[7,B]被链接到了[3,A]的前面，解决完[7,B]之后，就须要解决[7,B]的next了啊，而通过thread2的resize之后，[7,B]的next变为了[3,A]，此时，[3,A]和[7,B]造成了环形链表，在get的时候，如果get的key的桶索引和[3,A]和[7,B]一样，那么就会陷入死循环。

如果在取链表的时候从头开始取（当初是从尾部开始取）的话，则能够保障节点之间的程序，那样就不存在这样的问题了。

HashMap：JDK1.7 VS JDK1.8

JDK1.8次要解决或优化了一下问题：

  • resize 扩容优化
  • 引入了红黑树，目标是防止单条链表过长而影响查问效率
  • 解决了多线程死循环问题，但仍是非线程平安的，多线程时可能会造成数据失落问题
不同JDK 1.7JDK 1.8
存储构造数组 + 链表数组 + 链表 + 红黑树
初始化形式独自函数：inflateTable()间接集成到了扩容函数resize()中
hash值计算形式扰动解决 = 9次扰动 = 4次位运算 + 5次异或运算扰动解决 = 2次扰动 = 1次位运算 + 1次异或运算
存放数据的规定无抵触时，寄存数组；抵触时，寄存链表无抵触时，寄存数组；抵触 & 链表长度 < 8：寄存单链表；抵触 & 链表长度 > 8：树化并寄存红黑树
插入数据形式头插法（先将原地位的数据移到后1位，再插入数据到该地位）尾插法（直接插入到链表尾部/红黑树）
扩容后存储地位的计算形式全副依照原来办法进行计算（即hashCode ->> 扰动函数 ->> (h&length-1)）依照扩容后的法则计算（即扩容后的地位=原地位 or 原地位 + 旧容量

Hashtable

Hashtable 和 HashMap 都是散列表，也是用”拉链法“实现的哈希表。保留数据和 JDK7 中的 HashMap 一样，是 Entity 对象，只是 Hashtable 中的简直所有的 public 办法都是 synchronized 的，而有些办法也是在外部通过 synchronized 代码块来实现，效率必定会升高。且 put() 办法不容许空值。

HashMap 和 Hashtable 的区别

  1. 线程是否平安： HashMap 是非线程平安的，HashTable 是线程平安的；HashTable 外部的办法根本都通过 synchronized 润饰。（如果你要保障线程平安的话就应用 ConcurrentHashMap 吧！）；
  2. 效率： 因为线程平安的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 根本被淘汰，不要在代码中应用它；
  3. 对Null key 和Null value的反对： HashMap 中，null 能够作为键，这样的键只有一个，能够有一个或多个键所对应的值为 null。。然而在 HashTable 中 put 进的键值只有有一个 null，间接抛出 NullPointerException。

  4. 初始容量大小和每次裁减容量大小的不同 ：

    ① 创立时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次裁减，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次裁减，容量变为原来的2倍。

    ② 创立时如果给定了容量初始值，那么 Hashtable 会间接应用你给定的大小，而 HashMap 会将其裁减为2的幂次方大小。也就是说 HashMap 总是应用2的幂次方作为哈希表的大小,前面会介绍到为什么是2的幂次方。

  5. 底层数据结构： JDK1.8 当前的 HashMap 在解决哈希抵触时有了较大的变动，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以缩小搜寻工夫。Hashtable 没有这样的机制。
  6. HashMap的迭代器（Iterator）是fail-fast迭代器，然而 Hashtable的迭代器（enumerator）不是 fail-fast的。如果有其它线程对HashMap进行的增加/删除元素，将会抛出ConcurrentModificationException，但迭代器自身的remove办法移除元素则不会抛出异样。这条同样也是 Enumeration 和 Iterator 的区别。

理解过 LinkedHashMap、TreeMap 吗

LinkedHashMap属于HashMap的子类，与HashMap的区别在于LinkedHashMap保留了记录插入的程序。TreeMap实现了SortedMap接口，TreeMap 有能力对插入的记录依据 key 排序，默认依照升序排序，也能够自定义比拟项，在应用 TreeMap 的时候，key 该当实现 Comparable。

ConcurrentHashMap

HashMap 在多线程状况下，在 put 的时候，插入的元素超过了容量（由负载因子决定）的范畴就会触发扩容操作，就是 resize，这个会从新将原数组的内容从新 hash 到新的扩容数组中，在多线程的环境下，存在同时其余的元素也在进行 put 操作，如果 hash 值雷同，可能呈现同时在同一数组下用链表示意，造成闭环，导致在 get 时会呈现死循环，所以 HashMap 是线程不平安的。(可参考：https://www.jianshu.com/p/e2f75c8cce01）

Hashtable，是线程平安的，它在所有波及到多线程操作的都加上了synchronized关键字来锁住整个table，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是平安的，然而无疑是效率低下的。

JDK1.7 实现

Hashtable 容器在竞争强烈的并发环境下体现出效率低下的起因，是因为所有拜访 Hashtable 的线程都必须竞争同一把锁，那如果容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程拜访容器里不同数据段的数据时，线程间就不会存在锁竞争，这就是 ConcurrentHashMap 所应用的锁分段技术。

在 JDK1.7 版本中，ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。Segment 数组的意义就是将一个大的 table 宰割成多个小的 table 来进行加锁。每一个 Segment 元素存储的是 HashEntry数组+链表，这个和 HashMap 的数据存储构造一样。

ConcurrentHashMap 类中蕴含两个动态外部类 HashEntry 和 Segment。
HashEntry 用来封装映射表的键值对，Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中蕴含由若干个 Segment 对象组成的数组。每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行批改时，必须首先取得它对应的 Segment 锁。

Segment 类

Segment 类继承于 ReentrantLock 类，从而使得 Segment 对象能充当可重入锁的角色。一个 Segment 就是一个子哈希表，Segment 里保护了一个 HashEntry 数组，并发环境下，对于不同 Segment 的数据进行操作是不必思考锁竞争的。

从源码能够看到，Segment 外部类和咱们上边看到的 HashMap 很类似。也有负载因子，阈值等各种属性。

static final class Segment<K,V> extends ReentrantLock implements Serializable {    static final int MAX_SCAN_RETRIES =    Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;  transient volatile HashEntry<K,V>[] table;  transient int count;  transient int modCount;  //记录批改次数  transient int threshold;  final float loadFactor;  Segment(float lf, int threshold, HashEntry<K,V>[] tab) {    this.loadFactor = lf;    this.threshold = threshold;    this.table = tab;  }  //put 办法会有加锁操作，  final V put(K key, int hash, V value, boolean onlyIfAbsent) {    HashEntry<K,V> node = tryLock() ? null :                scanAndLockForPut(key, hash, value);    // ...  }  @SuppressWarnings("unchecked")  private void rehash(HashEntry<K,V> node) {    // ...  }  private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {         //...  }  private void scanAndLock(Object key, int hash) {         //...  }  final V remove(Object key, int hash, Object value) {    //...  }  final boolean replace(K key, int hash, V oldValue, V newValue) {      //...  }  final V replace(K key, int hash, V value) {    //...  }  final void clear() {        //...  }}

HashEntry 类

HashEntry 是目前最小的逻辑处理单元。一个 ConcurrentHashMap 保护一个 Segment 数组，一个 Segment 保护一个 HashEntry 数组。

static final class HashEntry<K,V> {  final int hash;  final K key;  volatile V value;   // value 为 volatie 类型，保障可见  volatile HashEntry<K,V> next;    //...}

ConcurrentHashMap 类

默认的状况下，每个 ConcurrentHashMap 类会创立16个并发的 segment，每个 segment 外面蕴含多个 Hash表，每个 Hash 链都是由 HashEntry 节点组成的。

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>        implements ConcurrentMap<K, V>, Serializable {  //默认初始容量为 16，即初始默认为 16 个桶  static final int DEFAULT_INITIAL_CAPACITY = 16;  static final float DEFAULT_LOAD_FACTOR = 0.75f;  //默认并发级别为 16。该值示意以后更新线程的估计数  static final int DEFAULT_CONCURRENCY_LEVEL = 16;    static final int MAXIMUM_CAPACITY = 1 << 30;  static final int MIN_SEGMENT_TABLE_CAPACITY = 2;    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative    static final int RETRIES_BEFORE_LOCK = 2;  final int segmentMask;  //段掩码,次要为了定位Segment  final int segmentShift;  final Segment<K,V>[] segments;   //骨干就是这个分段锁数组    //结构器  public ConcurrentHashMap(int initialCapacity,                             float loadFactor, int concurrencyLevel) {        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)            throw new IllegalArgumentException();       //MAX_SEGMENTS 为1<<16=65536，也就是最大并发数为65536        if (concurrencyLevel > MAX_SEGMENTS)            concurrencyLevel = MAX_SEGMENTS;        // 2的sshif次方等于ssize，例:ssize=16,sshift=4;ssize=32,sshif=5        int sshift = 0;        // ssize 为segments数组长度，依据concurrentLevel计算得出        int ssize = 1;        while (ssize < concurrencyLevel) {            ++sshift;            ssize <<= 1;        }        this.segmentShift = 32 - sshift;        this.segmentMask = ssize - 1;        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        int c = initialCapacity / ssize;        if (c * ssize < initialCapacity)            ++c;        int cap = MIN_SEGMENT_TABLE_CAPACITY;        while (cap < c)            cap <<= 1;        // 创立segments数组并初始化第一个Segment，其余的Segment提早初始化        Segment<K,V> s0 =            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),                             (HashEntry<K,V>[])new HashEntry[cap]);        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]        this.segments = ss;    }}

put() 办法

  1. 定位segment并确保定位的Segment已初始化
  2. 调用 Segment的 put 办法。
public V put(K key, V value) {  Segment<K,V> s;  //concurrentHashMap不容许key/value为空  if (value == null)    throw new NullPointerException();  //hash函数对key的hashCode从新散列，防止差劲的不合理的hashcode，保障散列平均  int hash = hash(key);  //返回的hash值无符号右移segmentShift位与段掩码进行位运算，定位segment  int j = (hash >>> segmentShift) & segmentMask;  if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck       (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment    s = ensureSegment(j);  return s.put(key, hash, value, false);}

get() 办法

get办法无需加锁，因为其中波及到的共享变量都应用volatile润饰，volatile能够保障内存可见性，所以不会读取到过期数据

public V get(Object key) {  Segment<K,V> s; // manually integrate access methods to reduce overhead  HashEntry<K,V>[] tab;  int h = hash(key);  long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;  if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&      (tab = s.table) != null) {    for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile         (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);         e != null; e = e.next) {      K k;      if ((k = e.key) == key || (e.hash == h && key.equals(k)))        return e.value;    }  }  return null;}

JDK1.8 实现

ConcurrentHashMap 在 JDK8 中进行了微小改变，光是代码量就从1000多行减少到6000行！1.8 摒弃了Segment(锁段)的概念，采纳了 CAS + synchronized 来保障并发的安全性。

能够看到，和 HashMap 1.8 的数据结构很像。底层数据结构扭转为采纳数组+链表+红黑树的数据模式。

和HashMap1.8雷同的一些中央

  • 底层数据结构统一
  • HashMap初始化是在第一次put元素的时候进行的，而不是init
  • HashMap的底层数组长度总是为2的整次幂
  • 默认树化的阈值为 8，而链表化的阈值为 6（当低于这个阈值时，红黑树转成链表）
  • hash算法也很相似，但多了一步& HASH_BITS，该步是为了打消最高位上的负符号，hash的负在ConcurrentHashMap中有非凡意义示意在扩容或者是树节点
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hashstatic final int spread(int h) {    return (h ^ (h >>> 16)) & HASH_BITS;}

一些要害属性

private static final int MAXIMUM_CAPACITY = 1 << 30; //数组最大大小 同HashMapprivate static final int DEFAULT_CAPACITY = 16;//数组默认大小static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //数组可能最大值，须要与toArray（）相干办法关联private static final int DEFAULT_CONCURRENCY_LEVEL = 16; //兼容旧版保留的值，默认线程并发度，相似信号量private static final float LOAD_FACTOR = 0.75f;//默认map扩容比例，理论用(n << 1) - (n >>> 1)代替了更高效static final int TREEIFY_THRESHOLD = 8; // 链表转树阀值，大于8时static final int UNTREEIFY_THRESHOLD = 6; //树转链表阀值，小于等于6（tranfer时，lc、hc=0两个计数器别离++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）。【仅在扩容tranfer时才可能树转链表】static final int MIN_TREEIFY_CAPACITY = 64;private static final int MIN_TRANSFER_STRIDE = 16;//扩容转移时的最小数组分组大小private static int RESIZE_STAMP_BITS = 16;//本类中没提供批改的办法 用来依据n生成地位一个相似工夫戳的性能private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // 2^15-1，help resize的最大线程数private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // 32-16=16，sizeCtl中记录size大小的偏移量static final int MOVED = -1; // hash for forwarding nodes（forwarding nodes的hash值）、标示位static final int TREEBIN = -2; // hash for roots of trees（树根节点的hash值）static final int RESERVED = -3; // ReservationNode的hash值static final int HASH_BITS = 0x7fffffff; // 用在计算hash时进行安位与计算打消负hashstatic final int NCPU = Runtime.getRuntime().availableProcessors(); // 可用处理器数量/* ---------------- Fields -------------- */transient volatile Node<K,V>[] table; //装载Node的数组，作为ConcurrentHashMap的数据容器，采纳懒加载的形式，直到第一次插入数据的时候才会进行初始化操作，数组的大小总是为2的幂次方。private transient volatile Node<K,V>[] nextTable; //扩容时应用，平时为null，只有在扩容的时候才为非null/*** 实际上保留的是hashmap中的元素个数  利用CAS锁进行更新但它并不必返回以后hashmap的元素个数 */private transient volatile long baseCount;/***该属性用来管制table数组的大小，依据是否初始化和是否正在扩容有几种状况：*当值为正数时：如果为-1示意正在初始化，如果为-N则示意以后正有N-1个线程进行扩容操作；*当值为负数时：如果以后数组为null的话示意table在初始化过程中，sizeCtl示意为须要新建数组的长度；若曾经初始化了，示意以后数据容器（table数组）可用容量也能够了解成临界值（插入节点数超过了该临界值就须要扩容），具体指为数组的长度n 乘以 加载因子loadFactor；当值为0时，即数组长度为默认初始值。*/private transient volatile int sizeCtl;

put() 办法

  1. 首先会判断 key、value是否为空，如果为空就抛异样！
  2. spread()办法获取hash，减小hash抵触
  3. 判断是否初始化table数组，没有的话调用initTable()办法进行初始化
  4. 判断是否能间接将新值插入到table数组中
  5. 判断以后是否在扩容，MOVED为-1阐明以后ConcurrentHashMap正在进行扩容操作，正在扩容的话就进行帮助扩容

  6. 当table[i]为链表的头结点，在链表中插入新值，通过synchronized (f)的形式进行加锁以实现线程安全性。

    1. 在链表中如果找到了与待插入的键值对的key雷同的节点，就间接笼罩
    2. 如果没有找到的话，就间接将待插入的键值对追加到链表的开端
  7. 当table[i]为红黑树的根节点，在红黑树中插入新值/笼罩旧值
  8. 依据以后节点个数进行调整，否须要转换成红黑树(个数大于等于8，就会调用treeifyBin办法将tabel[i]第i个散列桶拉链转换成红黑树)
  9. 对以后容量大小进行查看，如果超过了临界值（理论大小*加载因子）就进行扩容
final V putVal(K key, V value, boolean onlyIfAbsent) {    // key 和 value 均不容许为 null    if (key == null || value == null) throw new NullPointerException();    // 依据 key 计算出 hash 值    int hash = spread(key.hashCode());    int binCount = 0;    for (Node<K,V>[] tab = table;;) {        Node<K,V> f; int n, i, fh;         // 判断是否须要进行初始化        if (tab == null || (n = tab.length) == 0)            tab = initTable();        // f 即为以后 key 定位出的 Node，如果为空示意以后地位能够写入数据，利用 CAS 尝试写入，失败则自旋保障胜利        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {            if (casTabAt(tab, i, null,                         new Node<K,V>(hash, key, value, null)))                break;                   // no lock when adding to empty bin        }        // 如果以后地位的 hashcode == MOVED == -1,则须要进行扩容        else if ((fh = f.hash) == MOVED)            tab = helpTransfer(tab, f);        // 如果都不满足，则利用 synchronized 锁写入数据        else {          // 剩下状况又分两种，插入链表、插入红黑树            V oldVal = null;          //采纳同步内置锁实现并发管制            synchronized (f) {                if (tabAt(tab, i) == f) {                    // 如果 fh=f.hash >=0，以后为链表，在链表中插入新的键值对                    if (fh >= 0) {                        binCount = 1;                      //遍历链表，如果找到对应的 node 节点，批改 value,否则间接在链表尾部退出节点                        for (Node<K,V> e = f;; ++binCount) {                            K ek;                            if (e.hash == hash &&                                ((ek = e.key) == key ||                                 (ek != null && key.equals(ek)))) {                                oldVal = e.val;                                if (!onlyIfAbsent)                                    e.val = value;                                break;                            }                            Node<K,V> pred = e;                            if ((e = e.next) == null) {                                pred.next = new Node<K,V>(hash, key,                                                          value, null);                                break;                            }                        }                    }                    // 以后为红黑树，将新的键值对插入到红黑树中                    else if (f instanceof TreeBin) {                        Node<K,V> p;                        binCount = 2;                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                                       value)) != null) {                            oldVal = p.val;                            if (!onlyIfAbsent)                                p.val = value;                        }                    }                }            }            // 插入完键值对后再依据理论大小看是否须要转换成红黑树            if (binCount != 0) {                if (binCount >= TREEIFY_THRESHOLD)                    treeifyBin(tab, i);                if (oldVal != null)                    return oldVal;                break;            }        }    }    // 对以后容量大小进行查看，如果超过了临界值（理论大小*加载因子）就须要扩容     addCount(1L, binCount);    return null;}

咱们能够发现 JDK8 中的实现也是锁拆散的思维，只是锁住的是一个Node，而不是JDK7中的Segment，而锁住Node之前的操作是无锁的并且也是线程平安的，建设在之前提到的原子操作上。

get() 办法

get办法无需加锁，因为其中波及到的共享变量都应用volatile润饰，volatile能够保障内存可见性，所以不会读取到过期数据

public V get(Object key) {  Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;  int h = spread(key.hashCode());  // 判断数组是否为空  if ((tab = table) != null && (n = tab.length) > 0 &&      (e = tabAt(tab, (n - 1) & h)) != null) {    // 判断node 节点第一个元素是不是要找的，如果是间接返回    if ((eh = e.hash) == h) {      if ((ek = e.key) == key || (ek != null && key.equals(ek)))        return e.val;    }    // // hash小于0,阐明是非凡节点（TreeBin或ForwardingNode）调用find    else if (eh < 0)      return (p = e.find(h, key)) != null ? p.val : null;    // 不是下面的状况,那就是链表了,遍历链表    while ((e = e.next) != null) {      if (e.hash == h &&          ((ek = e.key) == key || (ek != null && key.equals(ek))))        return e.val;    }  }  return null;}

Hashtable 和 ConcurrentHashMap 的区别

ConcurrentHashMap 和 Hashtable 的区别次要体现在实现线程平安的形式上不同。

  • 底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采纳 分段的数组+链表 实现，JDK1.8 采纳的数据结构和 HashMap1.8 的构造相似，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构相似都是采纳 数组+链表 的模式，数组是 HashMap 的主体，链表则是次要为了解决哈希抵触而存在的；

  • 实现线程平安的形式（重要） ：

    • 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了宰割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程拜访容器里不同数据段的数据，就不会存在锁竞争，进步并发访问率。（默认调配16个Segment，比Hashtable效率进步16倍。） 到了 JDK1.8 的时候曾经摒弃了Segment的概念，而是间接用 Node 数组+链表/红黑树的数据结构来实现，并发管制应用 synchronized 和 CAS 来操作。（JDK1.6当前 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程平安的 HashMap，尽管在 JDK1.8 中还能看到 Segment 的数据结构，然而曾经简化了属性，只是为了兼容旧版本；
    • Hashtable(同一把锁) ：应用 synchronized 来保障线程平安，效率十分低下。当一个线程拜访同步办法时，其余线程也拜访同步办法，可能会进入阻塞或轮询状态，如应用 put 增加元素，另一个线程不能应用 put 增加元素，也不能应用 get，竞争越强烈效率越低。

Java疾速失败（fail-fast）和平安失败（fail-safe）区别

疾速失败（fail—fast）

在用迭代器遍历一个汇合对象时，如果遍历过程中对汇合对象的内容进行了批改（减少、删除、批改），则会抛出 ConcurrentModificationException。

原理：迭代器在遍历时间接拜访汇合中的内容，并且在遍历过程中应用一个 modCount 变量。汇合在被遍历期间如果内容发生变化，就会扭转 modCount 的值。每当迭代器应用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异样，终止遍历。

留神：这里异样的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果汇合发生变化时批改modCount 值刚好又设置为了 expectedmodCount 值，则异样不会抛出。因而，不能依赖于这个异样是否抛出而进行并发操作的编程，这个异样只倡议用于检测并发批改的 bug。

场景：java.util 包下的汇合类都是疾速失败的，不能在多线程下产生并发批改（迭代过程中被批改）。

平安失败（fail—safe）

采纳平安失败机制的汇合容器，在遍历时不是间接在汇合内容上拜访的，而是先复制原有汇合内容，在拷贝的汇合上进行遍历。

原理：因为迭代时是对原汇合的拷贝进行遍历，所以在遍历过程中对原汇合所作的批改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

毛病：基于拷贝内容的长处是防止了 Concurrent Modification Exception，但同样地，迭代器并不能拜访到批改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的汇合拷贝，在遍历期间原汇合产生的批改迭代器是不晓得的。

场景：java.util.concurrent 包下的容器都是平安失败，能够在多线程下并发应用，并发批改。

疾速失败和平安失败是对迭代器而言的。

疾速失败：当在迭代一个汇合的时候，如果有另外一个线程在批改这个汇合，就会抛出ConcurrentModification异样，java.util 下都是疾速失败。

平安失败：在迭代时候会在汇合二层做一个拷贝，所以在批改汇合下层元素不会影响上层。在 java.util.concurrent 下都是平安失败

如何防止fail-fast ？

  • 在单线程的遍历过程中，如果要进行 remove 操作，能够调用迭代器 ListIterator 的 remove 办法而不是汇合类的 remove办法。看看 ArrayList 中迭代器的 remove 办法的源码，该办法不能指定元素删除，只能 remove 以后遍历元素。
public void remove() {    if (lastRet < 0)        throw new IllegalStateException();    checkForComodification();    try {        SubList.this.remove(lastRet);        cursor = lastRet;        lastRet = -1;        expectedModCount = ArrayList.this.modCount;  //    } catch (IndexOutOfBoundsException ex) {        throw new ConcurrentModificationException();    }}

  • 应用并发包(java.util.concurrent)中的类来代替 ArrayList 和 hashMap

    • CopyOnWriterArrayList 代替 ArrayList
    • ConcurrentHashMap 代替 HashMap

Iterator 和 Enumeration 区别

在 Java 汇合中，咱们通常都通过 “Iterator(迭代器)” 或 “Enumeration(枚举类)” 去遍历汇合。

public interface Enumeration<E> {    boolean hasMoreElements();    E nextElement();}
public interface Iterator<E> {    boolean hasNext();    E next();    void remove();}
  • 函数接口不同，Enumeration只有2个函数接口。通过Enumeration，咱们只能读取汇合的数据，而不能对数据进行批改。Iterator只有3个函数接口。Iterator除了能读取汇合的数据之外，也能数据进行删除操作。
  • Iterator反对 fail-fast机制，而Enumeration不反对。Enumeration 是 JDK 1.0 增加的接口。应用到它的函数包含 Vector、Hashtable 等类，这些类都是 JDK 1.0中退出的，Enumeration 存在的目标就是为它们提供遍历接口。Enumeration 自身并没有反对同步，而在 Vector、Hashtable 实现 Enumeration 时，增加了同步。
    而 Iterator 是 JDK 1.2 才增加的接口，它也是为了 HashMap、ArrayList 等汇合提供遍历接口。Iterator 是反对 fail-fast 机制的：当多个线程对同一个汇合的内容进行操作时，就可能会产生 fail-fast 事件

Comparable 和 Comparator 接口有何区别？

Java 中对汇合对象或者数组对象排序，有两种实现形式：

  • 对象实现Comparable 接口

    • Comparable 在 java.lang 包下，是一个接口，外部只有一个办法 compareTo()

      public interface Comparable<T> {    public int compareTo(T o);}
    • Comparable 能够让实现它的类的对象进行比拟，具体的比拟规定是依照 compareTo 办法中的规定进行。这种程序称为 天然程序。
    • 实现了 Comparable 接口的 List 或则数组能够应用 Collections.sort() 或者 Arrays.sort() 办法进行排序

  • 定义比拟器，实现 Comparator接口

    • Comparator 在 java.util 包下，也是一个接口，JDK 1.8 以前只有两个办法：

      public interface Comparator<T> {    public int compare(T lhs, T rhs);    public boolean equals(Object object);}

comparable 相当于外部比拟器。comparator 相当于内部比拟器

区别：

  • Comparator 位于 java.util 包下，而 Comparable 位于 java.lang 包下
  • Comparable 接口的实现是在类的外部（如 String、Integer曾经实现了 Comparable 接口，本人就能够实现比拟大小操作），Comparator 接口的实现是在类的内部（能够了解为一个是自已实现比拟，一个是内部程序实现比拟）

  • 实现 Comparable 接口要重写 compareTo 办法, 在 compareTo 办法外面实现比拟。一个曾经实现Comparable 的类的对象或数据，能够通过 Collections.sort(list) 或者 Arrays.sort(arr)实现排序。通过 Collections.sort(list,Collections.reverseOrder()) 对list进行倒序排列。

  • 实现Comparator须要重写 compare 办法

HashSet

HashSet 是用来存储没有反复元素的汇合类，并且它是无序的。HashSet 外部实现是基于 HashMap ，实现了 Set 接口。

从 HahSet 提供的结构器能够看出，除了最初一个 HashSet 的构造方法外，其余所有外部就是去创立一个 HashMap 。没有其余的操作。而最初一个构造方法不是 public 的，所以不对外公开。

HashSet如何查看反复

HashSet 的底层其实就是 HashMap，只不过咱们 HashSet 是实现了 Set 接口并且把数据作为 K 值，而 V 值始终应用一个雷同的虚值来保留，HashMap的 K 值自身就不容许反复，并且在 HashMap 中如果 K/V 雷同时，会用新的 V 笼罩掉旧的 V，而后返回旧的 V。

Iterater 和 ListIterator 之间有什么区别？

  • 咱们能够应用 Iterator来遍历 Set 和 List 汇合，而 ListIterator 只能遍历List
  • ListIterator有add办法，能够向List中增加对象，而Iterator不能
  • ListIterator和Iterator都有hasNext()和next()办法，能够实现程序向后遍历，然而ListIterator有hasPrevious()和previous()办法，能够实现逆向（程序向前）遍历。Iterator不能够
  • ListIterator能够定位以后索引的地位，nextIndex()和previousIndex()能够实现。Iterator没有此性能
  • 都可实现删除操作，然而 ListIterator能够实现对象的批改，set()办法能够实现。Iterator仅能遍历，不能批改

<img src="https://static01.imgkr.com/temp/ef920406f7274d06a9b203b6b03e3171.png" style="zoom:50%;" />

参考与感激

所有内容都是基于源码浏览和各种大佬之前总结的常识整顿而来，输出并输入，奥利给。

https://www.javatpoint.com/java-arraylist

https://www.runoob.com/java/java-collections.html

https://www.javazhiyin.com/21717.html

https://yuqirong.me/2018/01/31/LinkedList外部原理解析/

https://youzhixueyuan.com/the-underlying-structure-and-princi...

《HashMap源码详细分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源码详细分析-JDK1-8/

《ConcurrentHashMap1.7源码剖析》https://www.cnblogs.com/chengxiao/p/6842045.html

http://www.justdojava.com/2019/12/18/java-collection-15.1/

本文由mdnice多平台公布