当前位置 : 首页 » 文章分类 :  开发  »  Java面试准备-(02)集合框架

Java面试准备-(02)集合框架

Java面试准备笔记


java 集合框架

随笔分类 - Java集合
http://www.cnblogs.com/xiaoxi/category/929860.html

Java集合框架综述
http://www.importnew.com/16658.html

Java集合框架概述

在集合框架的类继承体系中,最顶层有两个接口:

  • Collection表示一组纯数据
  • Map表示一组key-value对

关系图如下:


Java集合框架关系图
Collection
    |-----List 有序(存储顺序和取出顺序一致),可重复
        |----ArrayList 线程不安全,底层使用数组实现,查询快,增删慢。效率高。
        |----LinkedList 线程不安全,底层用双向链表实现,查询慢,增删快。效率高。
        |----Vector 线程安全,底层使用数组实现,查询快,增删慢。效率低。
            |----Stack 先进后出栈。基本的push和pop方法,还有peek方法得到栈顶的元素
    |-----Set 元素不可重复,set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2,并且最多包含一个 null 元素。
        |--HashSet 底层是由HashMap实现的,通过对象的hashCode方法与equals方法来保证插入元素的唯一性,无序(存储顺序和取出顺序不一致)。
            |--LinkedHashSet 底层数据结构由哈希表和链表组成。哈希表保证元素的唯一性,链表保证元素有序。(存储和取出是一致)
        |--TreeSet 基于TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator 进行排序。
Map
    |-----HashMap 数组+链表实现,非线程同步,初始桶数量为16,loadfactor为0.75,
        |-----LinkedHashMap 非同步。保留插入的顺序。维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。
    |-----TreeMap 非同步。基于红黑树实现。 根据key值对k-v对排序,支持自然排序、定制排序,取决于使用的构造方法。
    |-----Hashtable 线程同步的。key,value都不能为null

Collection接口

Collection接口主要有三个子接口:

  • Set,表示不允许有重复元素的集合(A collection that contains no duplicate elements)
  • List,表示允许有重复元素的集合(An ordered collection (also known as a sequence))
  • Queue,JDK1.5新增,与上面两个集合类主要是的区分在于Queue主要用于存储数据,而不是处理数据。(A collection designed for holding elements prior to processing.)

简图如下:


Collection接口

List

有序,元素可重复的集合。

ArrayList

动态数组,允许任何符合规则的元素插入甚至包括null
初始容量为10,自动扩容,可指定初始容量
每次容量不足时,自增长度的一半,如下源码可知
int newCapacity = oldCapacity + (oldCapacity >> 1);

ArrayList擅长于随机访问。同时ArrayList是非同步的。

ArrayList的自动扩容机制

java自动增加ArrayList大小的思路是:向ArrayList添加对象时,原对象数目加1如果大于原底层数组长度,则以适当长度新
建一个原数组的拷贝,并修改原数组,指向这个新建数组。原数组自动抛弃(java垃圾回收机制会自动回收)。

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);
}
ArrayList如何序列化

通过对ArrayList源码的分析,可以知道ArrayList的数据存储都是依赖于elementData数组,它的声明为:
transient Object[] elementData;
注意transient修饰着elementData这个数组,表示ArrayList在序列化的时候,默认不会序列化这些数组元素。

那么ArrayList是怎么序列化的呢?
首先要知道:
如果一个类不仅实现了Serializable接口,而且定义了 readObject(ObjectInputStream in)和 writeObject(ObjectOutputStream out)方法,那么将按照如下的方式进行序列化和反序列化:
ObjectOutputStream会调用这个类的writeObject方法进行序列化,ObjectInputStream会调用相应的readObject方法进行反序列化。

那么ObjectOutputStream又是如何知道一个类是否实现了writeObject方法呢?又是如何自动调用该类的writeObject方法呢?
答案是:是通过反射机制实现的。

ArrayList中定义了readObject(ObjectInputStream in)和 writeObject(ObjectOutputStream out)方法,readObject源码如下:

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

可以看到,首先通过s.defaultWriteObject();对非transient变量进行了序列化。然后又通过

for (int i=0; i<size; i++) {
    s.writeObject(elementData[i]);
}

这个循环对数组中的有值的元素逐个进行了序列化操作。

为什么使用transient修饰elementData?

既然要将ArrayList的字段序列化(即将elementData序列化),那为什么又要用transient修饰elementData呢?
回想ArrayList的自动扩容机制,elementData数组相当于容器,当容器不足时就会再扩充容量,但是容器的容量往往都是大于或者等于ArrayList所存元素的个数。
比如,现在实际有了8个元素,那么elementData数组的容量可能是8x1.5=12,如果直接序列化elementData数组,那么就会浪费4个元素的空间,特别是当元素个数非常多时,这种浪费是非常不合算的。
所以ArrayList的设计者将elementData设计为transient,然后在writeObject方法中手动将其序列化,并且只序列化了实际存储的那些元素,而不是整个数组。
见源码:

// Write out all elements in the proper order.
for (int i=0; i<size; i++)
{
    s.writeObject(elementData[i]);
}

从源码中,可以观察到 循环时是使用 i<size 而不是 i<elementData.length,说明序列化时,只需实际存储的那些元素,而不是整个数组。

java ArrayList的序列化分析
https://www.cnblogs.com/vinozly/p/5171227.html

ArrayList的序列化与反序列化
http://blog.csdn.net/qfycc92/article/details/45370011


LinkedList

双向链表,不能随机访问,非同步的

LinkedList实现原理

LinkedList的实现原理总结如下:
①数据存储是基于双向链表实现的。

transient int size = 0;
transient Node<E> first; //双向链表首结点
transient Node<E> last; //双向链表尾结点

②插入数据很快。先是在双向链表中找到要插入节点的位置index,找到之后,再插入一个新节点。 双向链表查找index位置的节点时,有一个加速动作:若index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找。

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

③删除数据很快。先是在双向链表中找到要插入节点的位置index,找到之后,进行如下操作:node.previous.next = node.next;node.next.previous = node.previous;node = null 。查找节点过程和插入一样。
④获取数据很慢,需要从Head节点进行查找。
⑤遍历数据很慢,每次获取数据都需要从头开始。

Java LinkedList的实现原理详解
http://blog.csdn.net/guoweimelon/article/details/50800730

ArrayList和LinkedList区别

除了常规的随机访问、插入删除的区别外

搜狗面试时,问能否从操作系统角度说下区别:ArrayList是一段连续的内存,LinkedList是不连续的内存,所以ArrayList访问起来更快。

58面试时,问通过get(i)和迭代器访问,哪个更快,ArrayList适合get(i)随机访问,LinkedList适合迭代器顺序访问


Vector(同步的)

动态数组,线程同步的。操作与ArrayList几乎一样。
每次容量不足时,默认自增长度的一倍(如果不指定增量的话),如下源码可知
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
若不指定,capacityIncrement默认为0

Vector实现原理

Vector的数据结构和ArrayList差不多,它包含了3个成员变量:elementData , elementCount, capacityIncrement。
(01) elementData 是”Object[]类型的数组”,它保存了添加到Vector中的元素。elementData是个动态数组,如果初始化Vector时,没指定动态数组的大小,则使用默认大小10。随着Vector中元素的增加,Vector的容量也会动态增长,capacityIncrement是与容量增长相关的增长系数,具体的增长方式,请参考源码分析中的ensureCapacity()函数。
(02) elementCount 是动态数组的实际大小。
(03) capacityIncrement 是动态数组的增长系数。如果在创建Vector时,指定了capacityIncrement的大小;则,每次当Vector中动态数组容量增加时,增加的大小都是capacityIncrement。否则,将容量大小增加一倍。

Stack(同步的)

Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop方法,还有peek方法得到栈顶的元素


Set

Set是一种不包括重复元素的Collection。set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2。并且最多包含一个 null 元素。

举一个例子:对象A和对象B,本来是不同的两个对象,正常情况下它们是能够放入到Set里面的,但是如果对象A和B的都重写了hashcode和equals方法,并且重写后的hashcode和equals方法是相同的话。那么A和B是不能同时放入到Set集合中去的,也就是Set集合中的去重和hashcode与equals方法直接相关。

HashSet

基于HashMap实现。非同步的。
HashSet中是允许存入null值的,但是在HashSet中仅仅能够存入一个null值。
HashSet的实现方式大致如下,通过一个HashMap存储元素,元素是存放在HashMap的Key中,而Value统一使用一个Object对象。

HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)支持。它不保证set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用null元素。HashSet中不允许有重复元素,这是因为HashSet是基于HashMap实现的,HashSet中的元素都存放在HashMap的key上面,而value中的值都是统一的一个private static final Object PRESENT = new Object();。HashSet跟HashMap一样,都是一个存放链表的数组。

HashSet中add方法调用的是底层HashMap中的put()方法,而如果是在HashMap中调用put,首先会判断key是否存在,如果key存在则修改value值,如果key不存在这插入这个key-value。而在set中,因为value值没有用,也就不存在修改value值的说法,因此往HashSet中添加元素,首先判断元素(也就是key)是否存在,如果不存在这插入,如果存在着不插入,这样HashSet中就不存在重复值。

深入Java集合学习系列:HashSet的实现原理
https://www.cnblogs.com/xwdreamer/archive/2012/06/03/2532999.html

HashSet中怎样判断元素重复?

在hashset中不允许出现重复对象,元素的位置也是不确定的。在hashset中又是怎样判定元素是否重复的呢?在java的集合中,判断两个对象是否相等的规则是:
1.判断两个对象的hashCode是否相等
如果不相等,认为两个对象也不相等,完毕
如果相等,转入2
(这一点只是为了提高存储效率而要求的,其实理论上没有也可以,但如果没有,实际使用时效率会大大降低,所以我们这里将其做为必需的。)

2.判断两个对象用equals运算是否相等
如果不相等,认为两个对象也不相等
如果相等,认为两个对象相等(equals()是判断两个对象是否相等的关键)
为什么是两条准则,难道用第一条不行吗?不行,因为前面已经说了,hashcode()相等时,equals()方法也可能不等,所以必须用第2条准则进行限制,才能保证加入的为非重复元素。

Java提高篇——equals()与hashCode()方法详解
http://www.cnblogs.com/Qian123/p/5703507.html

LinkedHashSet

基于LinkedHashMap来实现。非同步。
有序的,使用链表维护元素的次序,也就是说,当遍历该集合时候,LinkedHashSet将会以元素的添加顺序访问集合的元素。

TreeSet

基于TreeMap实现,非同步。
有序集合,支持两种排序方式,自然排序和定制排序。


Map接口


Map接口

Map并不是一个真正意义上的集合(are not true collections),但是这个接口提供了三种“集合视角”(collection views ),使得可以像操作集合一样操作它们,具体如下:

  • 把map的内容看作key的集合(map’s contents to be viewed as a set of keys)
  • 把map的内容看作value的集合(map’s contents to be viewed as a collection of values)
  • 把map的内容看作key-value映射的集合(map’s contents to be viewed as a set of key-value mappings)

HashMap

基于Map接口实现、允许null键/值、非同步、不保证有序(比如插入的顺序)、也不保证序不随时间变化。
HashMap最多只允许一条记录的键为null,允许多条记录的值为null。

HashMap内部实现(Node[] table)

HashMap的是初始容量(默认16)指的是桶的数量,或者说数组的长度。初始容量以及resize后的新容量总是2幂值,即使构造时传入的值不是2的幂值也会强制装换为2的幂值。
负载因子是hashmap中当前 元素数量/初始容量 的一个上限(此上限代码中用threshold(容量×负载因子)来衡量)。当超过整个限度时,会把链表数组的长度增加,重新计算各个元素的位置(最耗性能)
就是说,如果把负载因子调的很高,16个桶的HashMap也能装下100个元素,当然这时性能下降。

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

    transient Node<K,V>[] table; //存储键值对的Node数组(桶),默认长度16
    transient int size;  //当前键值对数量
    transient int modCount;  //结构发生变化的次数,用于迭代器的快速失败机制
    int threshold; //最大数据量,等于table.length * loadFactor,超出时需要resize
    final float loadFactor; //负载因子,默认0.75
}

Node节点结构:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;  //链表的下一个node
    ...
}

HashMap初始化(懒加载,桶个数2^n)

HashMap的是初始容量(默认16)指的是桶的数量(table数组的长度),或者说数组的长度。初始容量以及resize后的新容量总是2幂值,即使构造时传入的值不是2的幂值也会强制装换为2的幂值。

值得注意的是,当我们自定义HashMap初始容量大小时,构造函数并非直接把我们定义的数值当做HashMap容量大小,而是把该数值当做参数调用方法tableSizeFor,然后把返回值作为HashMap的初始容量大小:

/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

该方法会返回一个大于等于当前参数的2的倍数,因此HashMap中的table数组的容量大小总是2的倍数。

HashMap使用的是懒加载,构造完HashMap对象后,只要不进行put 方法插入元素之前,HashMap并不会去初始化或者扩容table:

public V put(K key, V value) {
    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;
    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 {
        ...
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

在putVal方法第8、9行我们可以看到,当首次调用put方法时,HashMap会发现table为空然后调用resize方法进行初始化
在putVal方法第16、17行我们可以看到,当添加完元素后,如果HashMap发现size(元素总数)大于threshold(阈值),则会调用resize方法进行扩容

Java HashMap的扩容
https://www.cnblogs.com/KingIceMou/p/6976574.html


合理选择初始容量

当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。

那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过 数组大小×loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16×0.75=12的时候,就把数组的大小扩展为2×16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75×1000 < 1000, 也就是说为了让0.75 × size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了问题,也避免了resize的问题。

在设置初始容量时应该考虑到映射中所需的条目数及其负载因子,以便最大限度的减少rehash操作次数。如果初始容量(桶的个数)大于最大条目数除以加载因子(初始容量乘以负载因子应该大于预估的最大元素数),则不会发生rehash操作。

Java HashMap提高性能和原理
http://blog.csdn.net/changlei_shennan/article/details/78680331

问题:给一组key{1,2,…,10},创建一个HashMap,指定初始容量为5,hash函数是key左移两位(<<1),在纸上画出来是怎么存储的?
需要考虑:
1、初始容量是5吗?
2、put过程中需要resize吗?
3、resize后是什么样的?


put方法流程与源码分析

put方法大致的思路为:
对key的hashCode()做hash,然后再计算index;
如果没碰撞直接放到bucket里;
如果碰撞了,以链表的形式存在buckets后;
如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD,默认为8),就把链表转换成红黑树;(仅在java8以上版本)
如果节点已经存在就替换old value(保证key的唯一性)
如果bucket满了(超过load factor*current capacity),就要resize。

具体试下:
1)根据key计算当前Node的hash值,用于定位对象在HashMap数组的哪个节点。
2)判断table有没有初始化,如果没有初始化,则调用resize()方法为table初始化容量,以及threshold的值。
3)根据hash值定位该key 对应的数组索引,如果对应的数组索引位置无值,则调用newNode()方法,为该索引创建Node节点
4)如果根据hash值定位的数组索引有Node,并且Node中的key和需要新增的key相等,则将对应的value值更新。
5)如果在已有的table中根据hash找到Node,其中Node中的hash值和新增的hash相等,但是key值不相等的,那么创建新的Node,放到当前已存在的Node的链表尾部。
如果当前Node的长度大于8,则调用treeifyBin()方法扩大table数组的容量,或者将当前索引的所有Node节点变成TreeNode节点,变成TreeNode节点的原因是由于TreeNode节点组成的链表索引元素会快很多。
5)将当前的key-value 数量标识size自增,然后和threshold对比,如果大于threshold的值,则调用resize()方法,扩大当前HashMap对象的存储容量。
6)返回oldValue或者null。

HashMap put()方法源码jdk1.8:

public V put(K key, V value) {
    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;
  //如果是第一次调用,则会调用resize 初始化table 以及threshold
  if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;
  //如果对应的索引没有Node,则新建Node放到table里面。
  if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
  else {
      Node<K,V> e; K k;
      //如果hash值与已存在的hash相等,并且key相等,则准备更新对应Node的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 {
          //如果hash值一致,但是key不一致,那么将新的key-value添加到已有的Node的最后面
          for (int binCount = 0; ; ++binCount) {
              if ((e = p.next) == null) {
                  p.next = newNode(hash, key, value, null);
                  // 当某个节点的链表长度大于8,则扩大table 数组的长度或者将当前节点链表变成树节点链表
                  if (binCount >= TREEIFY_THRESHOLD - 1)
                      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;
          //hash值和key值相等的情况下,更新value值
          if (!onlyIfAbsent || oldValue == null)
              e.value = value;
          //留给LinkedHashMap实现
          afterNodeAccess(e);
          //返回旧的value
          return oldValue;
      }
  }
  //修改次数加1
  ++modCount;
  //判断table的容量是否需要扩展
  if (++size > threshold)
      resize();
  //留给LinkedHashMap扩展
  afterNodeInsertion(evict);
  return null;
}

HashMap源码分析(基于JDK8)
https://blog.csdn.net/fighterandknight/article/details/61624150


resize源码分析(jdk1.7)

jdk1.7 resize源码如下,传进来的newCapacity参数是2 * table.length,即两倍原数组大小

void 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[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable);                        //!!将数据转移到新的Entry数组里
    table = newTable;                          //HashMap的table属性引用新的Entry数组
    threshold = (int) (newCapacity * loadFactor);//修改阈值
}

transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里:

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]; //头插法,把i位置上的链表挂到e后面
                newTable[i] = e;      //将元素放在数组上
                e = next;            //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

static int indexFor(int h, int length) {
    return h & (length - 1);
}

jdk1.8中:

newCap = oldCap << 1;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

resize后table大小变为原来的两倍

Java HashMap中在resize()时候的rehash,即再哈希法的理解
https://blog.csdn.net/qq_27093465/article/details/52270519


再哈希rehash和下标(桶)的计算

在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

而计算下标的时候,是通过hash值与桶个数按位与(使用&位操作,而非%求余)实现的:
(n - 1) & hash


Map的rehash计算

Java HashMap工作原理及实现
http://www.importnew.com/18633.html


HashMap中如何存储null key?(table[0])

HashMap可以允许插入null key和null value
HashTable和ConcurrentHashMap都不可以插入null key和null value

jdk1.8中HashMap的hash()方法中会判断key是否为null,如果key为null则直接返回0,所以null key是存储在table[0]中的,也就是数组的第一个元素。当key不为0时才会调用key.hashcode()进行rehash计算,所以也不会抛出异常。

如果value为null,和普通非空value一样,只是创建的Node节点中的value字段为null而已,没有任何影响。

HashMap中插入null key的过程分析
https://blog.csdn.net/glory1234work2115/article/details/50825503

HashTable和ConcurrentHashMap如何保证不插入null key和value?

HashTable和ConcurrentHashMap的put()方法会检查value是否null,如果为null则抛出空指针异常,之后会调用key.hashcode(),所以如果key为null,也会抛出空指针异常。所以HashTable和ConcurrentHashMap都不可以插入null key和null value

HashMap HashTable ConcurrentHashMap key和value是否可以null的问题 源码分析
https://blog.csdn.net/glory1234work2115/article/details/50830743

为什么这么设计?(是否支持并发)

ConcurrentHashmap和Hashtable都是支持并发的,这样会有一个问题,当你通过get(k)获取对应的value时,如果获取到的是null时,你无法判断,它是put(k,v)的时候value为null,还是这个key从来没有做过映射。HashMap是非并发的,可以通过contains(key)来做这个判断。而支持并发的Map在调用m.contains(key)和m.get(key),m可能已经不同了。

为什么Hashtable ConcurrentHashmap不支持key或者value为null
https://blog.csdn.net/gagewang1/article/details/54971965


自定义对象作为HashMap的键

如果要使用自己的类作为HashMap的键,必须同时重载hashCode()和equals()

在HashMap中,查找key的比较顺序为:
1、调用hashCode()方法计算object的哈希码,定位在哈希表中的哪个桶
2、若桶中有对象,调用equals()方法比较这些对象与object是否相等,若有相等的,重置value值,若没相等的,添加到链表末尾

显然,第一步就是要用到hashCode()方法,而第二步就是要用到equals()方法。在没有进行重载时,在这两步会默认调用Object类的这两个方法,而在Object中,Hash Code的计算方法是根据对象的地址进行计算的,那两个Person(“003”)的对象地址是不同的,所以它们的Hash Code也不同,自然HashMap也不会把它们当成是同一个key了。同时,在Object默认的equals()中,也是根据对象的地址进行比较,自然一个Person(“003”)和另一个Person(“003”)是不相等的。

理解了这一点,就很容易搞清楚为什么需要同时重载hashCode()和equals两个方法了。
重载hashCode()是为了对同一个key,能得到相同的Hash Code,这样HashMap就可以定位到我们指定的key上。
重载equals()是为了向HashMap表明当前对象和key上所保存的对象是相等的,这样我们才真正地获得了这个key所对应的这个键值对。

Java用自定义的类作为HashMap的key值实例
http://www.jb51.net/article/99636.htm

Java HashMap实现原理 源码剖析
https://www.cnblogs.com/haifeng1990/p/6262417.html


什么情况下性能退化为O(n)(HashMap性能分析)

HashMap使用key的hashCode()和equals()方法来将值划分到不同的桶里。桶的数量通常要比map中的记录的数量要稍大,这样每个桶包括的值会比较少(最好是一个)。当通过key进行查找时,我们可以在常数时间内迅速定位到某个桶(使用hashCode()对桶的数量进行取模)以及要找的对象。

如果多个hashCode()的值落到同一个桶内的时候,这些值是存储到一个链表中的。最坏的情况下,所有的key都映射到同一个桶中,这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

比如,HashMap的key类型是我们自定义的,重写了hashCode()和equals()方法,并且所有key类的实例都有相同的hashCode,如下:

class Key implements Comparable<Key> {
//...
@Override
public int hashCode() {
return 0;
}
}

此时所有元素都存储在一个桶内,get性能退化为O(n)

Java 8:HashMap的性能提升
http://www.importnew.com/14417.html


java8对HashMap的改进

JDK8中HashMap的新特性,如果某个桶中的链表记录过大的话(默认是TREEIFY_THRESHOLD = 8),就会把这个链动态变成红黑二叉树,使查询最差复杂度由O(N)变成了O(logN)。

如果某个桶中的记录过大的话(当前是TREEIFY_THRESHOLD = 8),HashMap会动态的使用一个专门的treemap实现来替换掉它。

它是如何工作的?
前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面,这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树,使用哈希值作为树的分支变量,如果两个哈希值不等,但指向同一个桶的话,较大的那个会插入到右子树里。如果哈希值相等,HashMap希望key值最好是实现了Comparable接口的,这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的,不过如果实现了当然最好。如果没有实现这个接口,在出现严重的哈希碰撞的时候,你就并别指望能获得性能提升了。


为什么HashMap是线程不安全的?

个人觉得HashMap在并发时可能出现的问题主要是两方面,
首先如果多个线程同时使用put方法添加元素,而且假设正好存在两个put的key发生了碰撞(hash值一样),那么根据HashMap的实现,这两个key会添加到数组的同一个位置,这样最终就会发生其中一个线程的put的数据被覆盖。
第二就是如果多个线程同时检测到元素个数超过数组大小*loadFactor,这样就会发生多个线程同时对Node数组进行扩容,都在重新计算元素位置以及复制数据,但是最终只有一个线程扩容后的数组会赋给table,也就是说其他线程的都会丢失,并且各自线程put的数据也丢失。

关于HashMap线程不安全这一点,《Java并发编程的艺术》一书中是这样说的:
HashMap在并发执行put操作时会引起死循环,导致CPU利用率接近100%。因为多线程会导致HashMap的Node链表形成环形数据结构,一旦形成环形数据结构,Node的next节点永远不为空,就会在获取Node时产生死循环。

如何线程安全的使用HashMap
http://www.importnew.com/21396.html

hashMap线程不安全的原因及表现
http://blog.csdn.net/vip_wangsai/article/details/70182933


如何线程安全的使用HashMap?

1、使用Hashtable(不推荐,synchronized)

1、使用 java.util.Hashtable 类,此类是线程安全的。但效率很低。因此是不推荐的。

2、使用Collections包装(不推荐,synchronized)

2、使用 java.util.Collections.synchronizedMap(Map<K,V>) 方法进行封装。

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    return new SynchronizedMap<K,V>(m);
    }

private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
    private final Map<K,V> m;    // Backing Map
    final Object      mutex;    // Object on which to synchronize

        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }

        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        }
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        }
}

从实现源代码可以发现,其封装的本质和 Hashtable 的实现是完全一致的,即对原Map本身的方法进行加锁,加锁的对象或者为外部指定共享对象mutex,或者为包装后的线程安全的Map本身。Hashtable 可以理解为 SynchronizedMap mutex=null 时候的特殊情况。因此这种同步方式的执行效率也是很低的。

既然已经有了Hashtable, 为什么还需要Collections 提供的这种静态方法包装哪?很简单,这种包装是Java Collection Framework提供的统一接口,除了用于 HashMap 外,还可以用于其他的Map。当然 除了对Map进行封装,Collections工具类还提供了对 Collection(比如Set,List)的线程安全实现封装方法,具体请参考 java.util.Colletions 实现,其原理和 SynchronizedMap 是一致的。

3、使用ConcurrentHashMap(推荐,分段加锁)

3、使用 java.util.concurrent.ConcurrentHashMap 类。
这是 HashMap 的线程安全版,同 Hashtable 相比,ConcurrentHashMap 不仅保证了访问的线程安全性,而且在效率上有较大的提高。

4、自己在代码中访问HashMap时加锁(不推荐,效率低)

4、自己在程序的关键方法或者代码段加锁,保证安全性,当然这是严重的不推荐。

Java - 线程安全的 HashMap 实现方法及原理
http://liqianglv2005.iteye.com/blog/2025016


WeakHashMap(弱引用版HashMap)

WeakHashMap与HashMap的用法基本类似。

区别:
1、HashMap的key保留了对实际对象的强引用,这意味着只要HashMap对象不被销毁,还HashMap的所有key所引用的对象就不会被垃圾回收,HashMap也不会自动删除这些key所对应的key-value对;
2、WeakHashMap的key只保留对实际对象的弱引用,这意味着如果WeakHashMap对象的key所引用的对象没有被其他强引用变量所引用,则这些key所引用的对象可能被垃圾回收,WeakHashMap也可能自动删除这些key所对应的key-value对。
3、WeakHashMap中的每个key对象只持有对实际对象的弱引用,因此,当垃圾回收了该key所对应的实际对象之后,WeakHashMap会自动删除该key对应的key-value对。

注意:如果需要使用WeakHashMap的key来保留对象的弱引用,则不要让该key所引用的对象具有任何强引用,否则将失去WeakHashMap的意义。

package com.map;

import java.util.WeakHashMap;

public class WeakHashMapTest {
public static void main(String[] args) {
    WeakHashMap wak = new WeakHashMap();
    //两个key都是匿名字符串对象(没有其他引用)
    wak.put(new String("数学"), new String("优良"));
    wak.put(new String("语文"), new String("良好"));

    //该key是一个系统缓存的字符串对象
    wak.put("java", new String("好")); //①
    System.out.println(wak);
    //{java=良好, 数学=优良, 语文=良好}

    //通知系统进行垃圾回收
    System.gc();
    System.runFinalization();
    System.out.println(wak);//{java=好}

}
}

结果上来看:当系统进行垃圾时,删除了WeakHashMap 对象的前两个key-value对,因为添加前两个key-value对时,这两个key都是匿名的字符串对象,WeakHashMap 只保留了对它们的弱引用,这样垃圾回收时会自动删除这两个key-value对。

WeakHashMap对象中①标示处的key是一个字符串直接量(系统会自动保留对该字符串对象的强引用),所以垃圾回收时不会回收它。

Java集合之WeakHashMap、IdentityHashMap、EnumMap介绍
https://blog.csdn.net/wxc880924/article/details/52683097


IdentityHashMap(允许key重复)

在Java中,有一种key值可以重复的map,就是IdentityHashMap。在IdentityHashMap中,判断两个键值k1和 k2相等的条件是 k1 == k2 。在正常的Map 实现(如 HashMap)中,当且仅当满足下列条件时才认为两个键 k1 和 k2 相等:(k1==null ? k2==null : e1.equals(e2))。

package com.map;

import java.util.IdentityHashMap;

public class IdentityHashMapTest {

    public static void main(String[] args) {
        IdentityHashMap idenmap = new IdentityHashMap();
        idenmap.put(new String("语文"), 80);
        idenmap.put(new String("语文"), 89);

        idenmap.put("java", 80);
        idenmap.put("java", 80);
        System.out.println(idenmap);
        //{语文=80, java=80, 语文=89}
    }
}

IdentityHashMap对象中添加了4个key-value对,前2个key-value对中的key是最新创建的字符串对象,它们通过==比较不相等,所以IdentityHashMap 会把他们当成2个key来处理;后2个key-value都是字符串直接量,而且它们的字符序列完全相同,Java使用常量池来管理字符串直接量,所以它们通过==比较返回true,IdentityHashMap 会认为它们是同一个key,因此只有一次可以添加成功。

Java集合之WeakHashMap、IdentityHashMap、EnumMap介绍
https://blog.csdn.net/wxc880924/article/details/52683097

java中key值可以重复的map:IdentityHashMap
https://www.cnblogs.com/it-deepinmind/p/7309522.html

HashMap中如何插入重复key?(重写equals)

put()方法实现:首先hash(key)得到key的hashcode(),hashmap根据获得的hashcode找到要插入的位置所在的链,在这个链里面放的都是hashcode相同的Entry键值对,在找到这个链之后,会通过equals()方法判断是否已经存在要插入的键值对,而这个equals比较的其实就是key。

java HashMap插入重复Key值问题
https://blog.csdn.net/intersting/article/details/72627353


EnumMap

EnumMap是一个与枚举类一起使用的Map实现,EnumMap中的所有key都必须是单个枚举类的枚举值。创建EnumMap时必须显示或隐式的指定它对应的枚举类。

EnumMap特征:
1、EnumMap在内部以数组形式保存,所以这种实现形式非常紧凑、高效。
2、EunmMap根据key的自然顺序(即枚举值在枚举类中的定义顺序)来维护key-value对的顺序。
3、EnumMap不允许使用null作为key,但允许使用null作为value。如果试图使用null作为key时将抛出NullpointerException。

如果只是查询是否包含值为null的key,或只是删除值为null的key,都不会抛出异常。

与普通的Map有所区别的是,创建EnumMap是必须指定一个枚举类,从而将该EnumMap和指定枚举类关联起来。

示例:

package com.map;

import java.util.EnumMap;

public class EnumMapTest {

    public static void main(String[] args) {

        EnumMap map = new EnumMap(Season.class);
        map.put(Season.SPRING, "春天");
        map.put(Season.SUMMER, "夏天");
        System.out.println(map);
        //{SPRING=春天, SUMMER=夏天}
    }
}

enum Season{
    SPRING,SUMMER,FAIL,WINTER
}

Java集合之WeakHashMap、IdentityHashMap、EnumMap介绍
https://blog.csdn.net/wxc880924/article/details/52683097


Hashtable(同步的)

Hashtable与HashMap类似,不同的是
1、HashMap允许key或value为null,Hashtable中key,value都不能为null;
2、是线程的同步的,即任一时刻只有一个线程能写Hashtable,因此也导致了Hashtale在写入时会比较慢。

Hashtable如何保证线程同步(安全)?

Hashtable的put,get,remove等方法都加了关键字synchronized,所以是线程同步的,任意时刻只有一个线程可以put,其他线程被阻塞。

public synchronized V get(Object key)
public synchronized V put(K key, V value)
public synchronized V remove(Object key)
public synchronized void clear()

但是也大大的降低了执行效率。因此是不推荐的。

Java - 线程安全的 HashMap 实现方法及原理
http://liqianglv2005.iteye.com/blog/2025016

HashTable与HashMap的异同点

HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口。主要的区别有:线程安全性,同步(synchronization),以及速度。
相同点:
(1)都实现了Map、Cloneable、java.io.Serializable接口。
(2)都是存储”键值对(key-value)”的散列表,而且都是采用拉链法实现的。
不同点:
(1)历史原因:HashTable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 。
(2)同步性:HashTable是线程安全的,也就是说是同步的,而HashMap是线程序不安全的,不是同步的 。
(3)对null值的处理:HashMap的key、value都可为null,HashTable的key、value都不可为null 。
(4)基类不同:HashMap继承于AbstractMap,而Hashtable继承于Dictionary。

JAVA中HashMap和Hashtable区别
https://www.cnblogs.com/lchzls/p/6714335.html


LinkedHashMap(按插入排序)

LinkedHashMap是HashMap的一个子类,它保留插入的顺序,如果需要输出的顺序和输入时的相同,那么就选用LinkedHashMap。

在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。

根据链表中元素的顺序可以分为:按插入顺序的链表,和按访问顺序(调用get方法)的链表。默认是按插入顺序排序,如果指定按访问顺序排序,那么调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。

类定义:

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

    transient LinkedHashMap.Entry<K,V> head; //双向链表的头节点
    transient LinkedHashMap.Entry<K,V> tail; //双向链表的尾结点
    final boolean accessOrder; //迭代顺序,true表示访问顺序,默认为false表示插入顺序
...
    public LinkedHashMap(int initialCapacity,
                        float loadFactor,
                        boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
...
}

LinkedHashMap继承自HashMap,所有构造方法都是通过调用父类的构造方法来创建对象的,默认创建时按插入顺序(accessOrder为false)。

下面HashMap类定义的基本成员在LinkedHashMap中也都有:

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

    transient Node<K,V>[] table; //存储键值对的Node数组(桶),默认长度16
    transient int size;  //当前键值对数量
    transient int modCount;  //结构发生变化的次数,用于迭代器的快速失败机制
    int threshold; //最大数据量,等于table.length * loadFactor,超出时需要resize
    final float loadFactor; //负载因子,默认0.75
}

结点Entry(加before和after指针构成双向链表)

LinkedHashMap中存储数据的Entry静态类继承自HashMap.Node:

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

HashMap.Node节点结构:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;  //链表的下一个node
    ...
}

除了Node中的hash,key,value,next外,LinkedHashMap的Entry中还增加了两个成员:before和after指针,分别指向双向链表的上一个、下一个结点

LinkedHashMap重新定义了数组中保存的元素Entry(继承于HashMap.Entry),该Entry除了保存当前对象的引用外,还保存了其上一个元素before和下一个元素after的引用,从而在哈希表的基础上又构成了双向链接列表。仍然保留next属性,所以既可像HashMap一样快速查找,用next获取该链表下一个Entry,也可以通过双向链接,通过after完成所有数据的有序迭代。

不要搞错了next和before、After,next是用于维护HashMap指定table位置上连接的Entry的顺序的,before、After是用于维护Entry插入的先后顺序的。


LinkedHashMap结构图

LinkedHashMap中的双向链表

第一张图为LinkedHashMap整体结构图,第二张图专门把循环双向链表抽取出来,直观一点,循环双向链表的头部存放的是最久访问的节点或最先插入的节点,尾部为最近访问的或最近插入的节点,迭代器遍历方向是从链表的头部开始到链表尾部结束,在链表尾部有一个空的header节点,该节点不存放key-value内容,为LinkedHashMap类的成员属性,循环双向链表的入口。

put方法(HashMap的put+重写addEntry)

LinkedHashMap并未重写父类HashMap的put方法,而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m) ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现。

也就是说,LinkedHashMap中是直接调用的HashMap的put方法,只不过重写了addEntry方法,put的时候如果需要新增加元素会调用addEntry方法。

HashMap中的put方法(jdk1.6)

//这个方法应该挺熟悉的,如果看了HashMap的解析的话
public V put(K key, V value) {
    //key为null的情况
    if (key == null)
        return putForNullKey(value);
    //通过key算hash,进而算出在数组中的位置,也就是在第几个桶中
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //查看桶中是否有相同的key值,如果有就直接用新值替换旧值,而不用再创建新的entry了
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    //上面度是熟悉的东西,最重要的地方来了,就是这个方法,LinkedHashMap执行到这里,addEntry()方法不会执行HashMap中的方法,
    //而是执行自己类中的addEntry方法,
    addEntry(hash, key, value, i);
    return null;
}

这里是一个多态,因为LinkedHashMap重写了addEntry方法,因此addEntry调用的是LinkedHashMap重写了的方法:

void addEntry(int hash, K key, V value, int bucketIndex) {

    //创建新的Entry,并插入到LinkedHashMap中
    createEntry(hash, key, value, bucketIndex);  // 重写了HashMap中的createEntry方法

    //双向链表的第一个有效节点(header后的那个节点)为最近最少使用的节点,这是用来支持LRU算法的
    Entry<K,V> eldest = header.after;
    //如果有必要,则删除掉该近期最少使用的节点,
    //这要看对removeEldestEntry的覆写,由于默认为false,因此默认是不做任何处理的。
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    } else {
        //扩容到原来的2倍
        if (size >= threshold)
            resize(2 * table.length);
    }
}

可以看到,addEntry中先通过removeEldestEntry()方法判断是否需要删除元素(默认直接返回false即不删除),如果需要的话通过removeEntryForKey()删除最久未使用元素(也就是头结点后的第一个元素,刚被访问的元素会被摘下来插入到末尾),所以只要重写removeEldestEntry()方法即可快速利用LinkedHashMap实现一个LRU缓存

看一下createEntry方法:

void createEntry(int hash, K key, V value, int bucketIndex) {
    // 向哈希表中插入Entry,这点与HashMap中相同
    //创建新的Entry并将其链入到数组对应桶的链表的头结点处,
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
    table[bucketIndex] = e;

    //在每次向哈希表插入Entry的同时,都会将其插入到双向链表的尾部,
    //这样就按照Entry插入LinkedHashMap的先后顺序来迭代元素(LinkedHashMap根据双向链表重写了迭代器)
    //同时,新put进来的Entry是最近访问的Entry,把其放在链表末尾 ,也符合LRU算法的实现
    e.addBefore(header);  //addBefore方法本质上是一个双向链表的插入操作
    size++;
}

总的来说,相比HashMap而言,LinkedHashMap在向哈希表添加一个键值对的同时,也会将其链入到它所维护的双向链表中,以便设定迭代顺序。

get方法(重写get方法,增加按访问排序调整)

LinkedHashMap重写了父类HashMap的get方法,实际在调用父类getEntry()方法取得查找的元素后,再判断当排序模式accessOrder为true时(即按访问顺序排序),先将当前节点从链表中移除,然后再将当前节点插入到链表尾部。由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失。

/**
* 通过key获取value,与HashMap的区别是:当LinkedHashMap按访问顺序排序的时候,会将访问的当前节点移到链表尾部(头结点的前一个节点)
*/
public V get(Object key) {
    // 调用父类HashMap的getEntry()方法,取得要查找的元素。
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    // 记录访问顺序。
    e.recordAccess(this);
    return e.value;
}

recordAccess源码如下,在HashMap的put和get方法中,会调用该方法,在HashMap中该方法为空

/**
* 在HashMap的put和get方法中,会调用该方法,在HashMap中该方法为空
* 在LinkedHashMap中,当按访问顺序排序时,该方法会将当前节点插入到链表尾部(头结点的前一个节点),否则不做任何事
*/
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //当LinkedHashMap按访问排序时
    if (lm.accessOrder) {
        lm.modCount++;
        //移除当前节点
        remove();
        //将当前节点插入到头结点前面
        addBefore(lm.header);
    }
}

/**
* 移除节点,并修改前后引用
*/
private void remove() {
    before.after = after;
    after.before = before;
}

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

LinkedHashMap如何实现有序?

LinkedHashMap的构造方法
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)
第三个参数accessOrder,false 基于插入顺序(默认),true 基于访问顺序(get一个元素后,这个元素被加到最后)

LinkedHashMap重写了HashMap中保存的元素Entry,增加了上一个元素的引用before和下一个元素的引用after,从而在哈希表的基础上又构成了双向循环链表。

若指定按访问顺序排序的话,每次访问(get和put都算访问)时都会把刚访问的元素移到双向链表的尾部,所以循环双向链表的头部存放的是最久访问的节点或最先插入的节点,尾部为最近访问的或最近插入的节点

如何实现的呢?
LinkedHashMap的put和get中都会调用recordAccess方法(jdk1.8中是afterNodeAccess方法)来将刚访问的元素移到双向链表末尾。

recordAccess中做了两件事情:
1、把待移动的Entry的前后Entry相连
2、把待移动的Entry移动到尾部

recordAccess源码如下,在HashMap的put和get方法中,会调用该方法,在HashMap中该方法为空

/**
* 在HashMap的put和get方法中,会调用该方法,在HashMap中该方法为空
* 在LinkedHashMap中,当按访问顺序排序时,该方法会将当前节点插入到链表尾部(头结点的前一个节点),否则不做任何事
*/
void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
    //当LinkedHashMap按访问排序时
    if (lm.accessOrder) {
        lm.modCount++;
        //移除当前节点
        remove();
        //将当前节点插入到头结点前面
        addBefore(lm.header);
    }
}

Java集合之LinkedHashMap - 平凡希
https://www.cnblogs.com/xiaoxi/p/6170590.html

Map 综述(二):彻头彻尾理解 LinkedHashMap
https://blog.csdn.net/justloveyou_/article/details/71713781


利用LinkedHashMap实现LRU缓存(重写removeEldestEntry)

LinkedHashMap的构造方法
public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)
第三个参数accessOrder,false 基于插入顺序(默认),true 基于访问顺序(get一个元素后,这个元素被加到最后)
将构造方法的第三个参数设为true,可自动按访问顺序排序。

put方法最后会调用addEntry,addEntry中先通过removeEldestEntry()方法判断是否需要删除元素(默认直接返回false即不删除),如果需要的话通过removeEntryForKey()删除最久未使用元素(也就是头结点后的第一个元素,刚被访问的元素会被摘下来插入到末尾),所以只要重写removeEldestEntry()方法即可快速利用LinkedHashMap实现一个LRU缓存

具体实现如下:

public class LRUCache extends LinkedHashMap
{
    private static final long serialVersionUID = 1L;
    protected int maxElements;//LRU的最大元素个数,即缓存的容量

    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }

    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }
}

构造方法中调用父类也就是LinkedHashMap的构造器,第三个参数设为true表示按访问顺序排序。
重写removeEldestEntry()方法,当size大于缓存容量是返回true,则put时会自动删除最久未使用的元素。也就是实现了LRU缓存。

Java集合之LinkedHashMap - 平凡希
https://www.cnblogs.com/xiaoxi/p/6170590.html


TreeMap(按key排序)

基于红黑树实现,每一个key-value节点作为红黑树的一个节点。

TreeMap存储时会进行排序的,会根据key来对key-value键值对进行排序,其中排序方式也是分为两种,一种是自然排序,一种是定制排序,具体取决于使用的构造方法。
默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。

Java TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序,key大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。

TreeMap底层通过红黑树(Red-Black tree)实现,也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。

出于性能原因,TreeMap是非同步的(not synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过Collections工具类将TreeMap包装成(wrapped)同步的

史上最清晰的红黑树讲解(上)
https://www.cnblogs.com/CarpenterLee/p/5503882.html


Collections和Arrays工具类

Collections.sort()方法内部是调用List.sort()方法,List.sort()方法内部是调用Arrays.sort()方法进行排序。

Arrays.sort(int[] a) 基本类型数组排序(双枢轴快速排序)

以下分析都是基于jdk1.8
Arrays中int数组的排序方法Arrays.sort(int[] a)源码如下:

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

其他long,short,char,byte,float,double类型数组的sort()方法也都是调用DualPivotQuicksort.sort()
但对于不同的基本类型,sort方法的实现又略有差异。

对于int数组来说:

  • 如果长度小于286,使用快速排序:
    • 如果长度小于47,使用插入排序
    • 否则(长度大于47小于286)使用双枢轴快速排序
  • 否则(长度大于286),检测数组的顺序性
    • 如果顺序连续性好,使用归并排序的变种TimSort算法。TimSort算法的核心在于利用数列中的部分有序。
    • 如果顺序连续性不好,使用双轴快排 + 成对插入排序。

JSE1.6及之前,该排序算法是一个经过调优的快速排序法
JSE1.7及之后,使用双枢轴快排

Java DualPivotQuickSort 双轴快速排序 源码 笔记
https://www.cnblogs.com/yuxiaofei93/p/5722714.html


Arrays.sort(Object[] a) 对象数组排序(TimSort)

以下分析都是基于jdk1.8

对于对象数组,

  • 如果长度小于32,使用折半插入排序
  • 如果长度大于32,使用归并排序的变种TimSort

Collections类中的sort源码:

public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

List接口中的default sort方法源码:

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

即先将list转化为数组a,对a利用Arrays.sort()排序,然后遍历数组a把每个元素set到list中

Arrays.sort(Object[] a)源码:

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);  //没有自己的比较器
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0); //有自己的比较器
    }
}

//没有自己的比较器时调用的方法
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

即除非指定使用遗留的归并排序,否则都使用TimSort.sort()排序

ComparableTimSort.sort()方法源码:

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
    assert a != null && lo >= 0 && lo <= hi && hi <= a.length;  //检查lo,hi的的准确性

    int nRemaining  = hi - lo;
    if (nRemaining < 2)  //当长度为0或1时永远都是已经排序状态
        return;  // Arrays of size 0 and 1 are always sorted

    // 当数组长度小于MIN_MERGE(32)的时候,就用一个"mini-TimSort"的方法排序,jdk1.7新加
    // If array is small, do a "mini-TimSort" with no merges
    if (nRemaining < MIN_MERGE) {
        // 找出最大的递增或者递减的个数,如果递减,则此段数组严格反一下方向
        int initRunLen = countRunAndMakeAscending(a, lo, hi);
        binarySort(a, lo, hi, lo + initRunLen); //二分插入排序
        return;
    }

    //数组长度大于32的情况
    /**
    * March over the array once, left to right, finding natural runs,
    * extending short natural runs to minRun elements, and merging runs
    * to maintain stack invariant.
    */
    ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        // Identify next run
        int runLen = countRunAndMakeAscending(a, lo, hi);

        // If run is short, extend to min(minRun, nRemaining)
        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen);
            runLen = force;
        }

        // Push run onto pending-run stack, and maybe merge
        ts.pushRun(lo, runLen);
        ts.mergeCollapse();

        // Advance to find next run
        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);

    // Merge all remaining runs to complete sort
    assert lo == hi;
    ts.mergeForceCollapse();
    assert ts.stackSize == 1;
}

Java源码之Arrays内部排序实现(timsort的实现)
https://blog.csdn.net/qq_25673113/article/details/60468364

Arrays.sort和Collections.sort实现原理解析
https://blog.csdn.net/u011410529/article/details/56668545


为什么不同类型采用不同的排序算法?

Arrays.sort()对基本类型数组和对象数组使用了不同的排序算法,在jdk8中:
1、如果是基本类型数组,例如int数组,长度小于47时使用插入排序,长度大于47小于286时使用双枢轴快速排序,长度大于286时对数组的顺序性进行判断,如果顺序性好使用归并排序的变种TimSort,如果顺序性不好使用双枢轴快速排序。
2、如果是对象数组,长度小于32时使用折半插入排序,长度大于32,使用归并排序的变种TimSort

为什么采用不同算法呢?
1、对Object类型进行排序。快速排序不稳定,对基本类型无影响,对Object类型有影响。归并排序稳定。
因为归并有一个快排没有的优点,就是归并排序是稳定的。对于整型数浮点数,稳定不稳定大概看不出来,但是对于对象,是否稳定很重要。

2、对大数组排序。快速排序的sort()采用递归实现,数组规模太大时会发生堆栈溢出,而归并排序sort()采用非递归实现,不存在此问题。

此外,快排在最坏情况下复杂度为O(n^2),归并排序在任何情况下时间复杂度都是O(nlogn)

为什么复杂对象不使用快速排序呢?
因为对于一个hashcode计算复杂的对象来说,移动的成本远低于比较的成本

jdk7/8对Arrays.sort()的优化?

Colletions.sort()实际会将list转为数组,然后调用Arrays.sort(),排完了再转回List。

JDK6中
Arrays.sort(),对原始类型(int[],double[],char[],byte[]),JDK6里用的是快速排序,对于对象类型(Object[]),JDK6则使用归并排序。为什么要用不同的算法呢?

JDK7的进步
到了JDK7,快速排序升级为双枢轴快排(双枢轴快排 vs 三路快排);归并排序升级为归并排序的改进版TimSort,一个JDK的自我进化。

JDK8的进步
再到了JDK8, 对大集合增加了Arrays.parallelSort()函数,使用fork-Join框架,充分利用多核,对大的集合进行切分然后再归并排序,而在小的连续片段里,依然使用TimSort与DualPivotQuickSort。


集合的线程安全

线程安全:就是当多线程访问时,采用了加锁的机制;即当一个线程访问该类的某个数据时,会对这个数据进行保护,其他线程不能对其访问,直到该线程读取完之后,其他线程才可以使用。防止出现数据不一致或者数据被污染的情况。

线程不安全:就是不提供数据访问时的数据保护,多个线程能够同时操作某个数据,从而出现数据不一致或者数据污染的情况。

线程安全 工作原理: jvm中有一个main memory对象,每一个线程也有自己的working memory,一个线程对于一个变量variable进行操作的时候, 都需要在自己的working memory里创建一个copy,操作完之后再写入main memory。
当多个线程操作同一个变量variable,就可能出现不可预知的结果。

而用synchronized的关键是建立一个监控monitor,这个monitor可以是要修改的变量,也可以是其他自己认为合适的对象(方法),然后通过给这个monitor加锁来实现线程安全,每个线程在获得这个锁之后,要执行完加载load到working memory 到 use && 指派assign 到 存储store 再到 main memory的过程。才会释放它得到的锁。这样就实现了所谓的线程安全。

vector,statck,Hashtable,Collections包装都是加synchronized

并且get方法也都加了synchronized

由于Vector中的add方法和get方法都进行了同步,因此,在有多个线程进行访问时,如果多个线程都只是进行读取操作,那么每个时刻就只能有一个线程进行读取,其他线程便只能等待,这些线程必须竞争同一把锁。

Java并发编程:同步容器 - 海子
http://www.cnblogs.com/dolphin0520/p/3933404.html

通过Collections的同步包装器变成线程安全的

Collections工具类提供了对所有集合进行线程安全包装的静态方法,例如:

static <T> List<T> synchronizedList(List<T> list) //返回指定List对象对应的线程安全的List 对象。
static <K, V> Map<K, V> synchronizedMap(Map<K, V> m) //返回指定Map对象对应的线程安全的Map对象。
static <T> Set<T> synchronizedSet(Set<T> s) //返回指定Set对象对应的线程安全的Set对象。

例如需要在多线程里使用线程安全的HashMap对象(如果需要把某个集合包装成线程安全的集合,则应该在创建之后立即包装),则可以采用如下代码:
HashMap m = Collections.synchronizedMap(new HashMap());

同步包装的原理是对原集合类本身的方法加锁,因此这种同步方式的执行效率是很低的。

使用concurrent包的线程安全集合类

java.util.concurrent包提供了ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentLinkedQueue、CopyOnWriteArrayList等线程安全的集合类,这些集合通过复杂的算法,通过允许并发的访问数据结构的不同部分来使竞争极小化。

比如HashMap对应的线程安全类ConcurrentHashMap
ArrayList对应的线程安全类CopyOnWriteArrayList


迭代器

每个集合类内部都含有Iterator<E> iterator()方法,该方法是返回集合中迭代器对象。获取迭代器对象后,就可以使用hasNext、next方法操作集合中的元素了(遍历)。如果仔细分析下,不难得出如下结论:

每个集合类内部都含有一个内部类,用来实现Iterator接口。集合类的iterator方法就是在获取内部类对象(迭代器对象),然后通过该对象调用hashNext和next方法实现遍历。

Iterator接口

ArrayList的Iterator

在ArrayList内部定义了一个内部类Itr,该类实现了Iterator接口。
在Itr中,有三个变量分别是
cursor:表示下一个元素的索引位置
lastRet:表示上一个元素的索引位置
expectModCount:预期被修改的次数
实现next()是通过get(cursor),然后cursor++,通过这样实现遍历。

ArrayList的ListIterator

Iterator只提供了删除元素的方法remove,如果我们想要在遍历的时候添加元素怎么办?
ListIterator接口继承了Iterator接口,它允许程序员按照任一方向遍历列表,迭代期间修改列表,并获得迭代器在列表中的当前位置。

Java集合Iterator迭代器的实现
http://www.cnblogs.com/xujian2014/p/5846128.html

实现Iterable接口的集合可通过foreach语句遍历

foreach是JDK1.5新增加的一个循环结构,foreach的出现是为了简化我们遍历集合的行为。

实现Iterable接口允许对象成为Foreach语句的目标。就可以通过foreach语句来遍历你的底层序列。

使用Foreach时对集合的结构进行修改会出现异常:
上面我们说了实现了Iterable接口的类就可以通过Foreach遍历,那是因为foreach要依赖于Iterable接口返回的Iterator对象,所以从本质上来讲,Foreach其实就是在使用迭代器,在使用foreach遍历时对集合的结构进行修改,和在使用Iterator遍历时对集合结构进行修改本质上是一样的。所以同样的也会抛出异常,执行快速失败机制。

深入理解Java中的迭代器
https://www.cnblogs.com/zyuze/p/7726582.html

为什么LinkedList用迭代器遍历更快?

for循环get(i),对于ArrayList可随机访问,对于LinkedList,每次get(i)都需要从头开始数到i
迭代器是顺序访问,使用迭代器遍历LinkedList是顺序遍历的,不用每次从头开始数

for循环与迭代器的对比,效率上各有各的优势:
ArrayList对随机访问比较快,而for循环中使用的get()方法,采用的即是随机访问的方法,因此在ArrayList里for循环快。
LinkedList则是顺序访问比较快,Iterator中的next()方法采用的是顺序访问方法,因此在LinkedList里使用Iterator较快。
主要还是要依据集合的数据结构不同的判断。

深入理解Java中的迭代器
https://www.cnblogs.com/zyuze/p/7726582.html

Enumeration和Iterator对比

(01) 函数接口不同
Enumeration只有2个函数接口。通过Enumeration,我们只能读取集合的数据,而不能对数据进行修改。
Iterator只有3个函数接口。Iterator除了能读取集合的数据之外,也能数据进行删除操作。

(02) 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事件。

使用Iterator来遍历集合时,应使用Iterator的remove()方法来删除集合中的元素,使用集合的remove()方法将抛出ConncurrentModificationException异常。

Java 集合系列18之 Iterator和Enumeration比较
http://www.cnblogs.com/skywang12345/p/3311275.html


fail-fast快速失败机制

实现原理

“快速失败”也就是fail-fast,它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时,有可能会产生fail-fast机制。记住是有可能,而不是一定。

ArrayList, HashMap等类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险(这就是为什么叫快速失败)。

迭代器的快速失败行为无法得到保证,它不能保证一定会出现该错误,但是快速失败操作会尽最大努力抛出ConcurrentModificationException异常,所以因此,为提高此类操作的正确性而编写一个依赖于此异常的程序是错误的做法,正确做法是:ConcurrentModificationException 应该仅用于检测 bug。

例如:假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。

fail-fast产生的原因就在于程序在对 collection 进行迭代时,某个线程对该 collection 在结构上对其做了修改,这时迭代器就会抛出 ConcurrentModificationException 异常信息,从而产生 fail-fast。

这一策略在源码中是通过modCount和expectedModCount实现的:

  • modCount顾名思义就是修改次数,是集合类本身的一个属性(比如ArrayList的modCount是在其父类 AbstractList 中定义的,HashMap的modCount是其本类的一个属性),对集合内容的修改都将增加这个值(例如ArrayList中无论add、remove、clear方法只要是涉及了改变ArrayList元素的个数的方法都会导致modCount加1)。
  • 而expectedModCount是在迭代器中定义的,在迭代器初始化过程中会将modCount赋值给expectedModCount,所以新获得一个迭代器时其expectedModCount值等于modCount

例如HashMap的HashIterator构造函数:

HashIterator() {
    expectedModCount = modCount;
    ...
}

又比如ArrayList的迭代器iterator()

private class Itr implements Iterator<E> {
    int cursor;      // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
}

迭代器在调用next()、remove()等方法时,都要判断迭代器自己的expectedModCount是否和集合类的modCount相等,如果不相等就表示已经有其他线程修改了集合结构(其实也不一定是其他线程,在使用迭代器遍历过程中如果直接通过集合的remove()(注意非迭代器的remove)等操作修改了集合结构也会导致两者不等),就抛出ConcurrentModificationException 异常,从而产生fail-fast机制。


fail-fast解决办法

方案一:在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList,这样就可以解决。但是不推荐,因为增删造成的同步锁可能会阻塞遍历操作。
方案二:使用CopyOnWriteArrayList来替换ArrayList。推荐使用该方案。

Java提高篇(三四)—–fail-fast机制
http://blog.csdn.net/chenssy/article/details/38151189

HashMap 多线程处理之 Fail-Fast机制
http://www.cnblogs.com/alexlo/archive/2013/03/14/2959233.html

关于快速报错fail-fast想说的之fail-fast的实现原理(一)
http://blog.csdn.net/fan2012huan/article/details/51076970

Hashtable支持fastfail机制吗?

Hashtable的iterator遍历方式支持fast-fail,用Enumeration不支持fast-fail


选择合适的集合类

容器类和Array(数组)的区别、择取
容器类仅能持有对象引用(指向对象的指针),而不是将对象信息copy一份至数列某位置。
一旦将对象置入容器内,便损失了该对象的型别信息。

  • 在各种Lists中,最好的做法是以ArrayList作为缺省选择。当插入、删除频繁时,使用LinkedList();
    Vector总是比ArrayList慢,所以要尽量避免使用。

  • 在各种Sets中,HashSet通常优于TreeSet(插入、查找)。只有当需要产生一个经过排序的序列,才用TreeSet。
    TreeSet存在的唯一理由:能够维护其内元素的排序状态。

  • 在各种Maps中
    HashMap用于快速查找。

  • 当元素个数固定,用Array,因为Array效率是最高的。

结论:最常用的是ArrayList,HashSet,HashMap,Array。而且,我们也会发现一个规律,用TreeXXX都是排序的。

注意:
1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。
2、Set和Collection拥有一模一样的接口。
3、List,可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个,get(0)…。(add/get)
4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。
5、Map用 put(k,v) / get(k),还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。
HashMap会利用对象的hashCode来快速找到key。
6、Map中元素,可以将key序列、value序列单独抽取出来。
使用keySet()抽取key序列,将map中的所有keys生成一个Set。
使用values()抽取value序列,将map中的所有values生成一个Collection。
为什么一个生成Set,一个生成Collection?那是因为,key总是独一无二的,value允许重复。

java的集合框架最全详解
https://www.cnblogs.com/565261641-fzh/p/5659783.html


上一篇 Java面试准备-(03)线程和并发

下一篇 MySQL-使用笔记

阅读
17,956
阅读预计71分钟
创建日期 2018-03-13
修改日期 2018-11-15
类别
目录
  1. java 集合框架
    1. Java集合框架概述
    2. Collection接口
      1. List
        1. ArrayList
          1. ArrayList的自动扩容机制
          2. ArrayList如何序列化
            1. 为什么使用transient修饰elementData?
        2. LinkedList
          1. LinkedList实现原理
          2. ArrayList和LinkedList区别
        3. Vector(同步的)
          1. Vector实现原理
        4. Stack(同步的)
      2. Set
        1. HashSet
          1. HashSet中怎样判断元素重复?
        2. LinkedHashSet
        3. TreeSet
    3. Map接口
      1. HashMap
        1. HashMap内部实现(Node[] table)
        2. HashMap初始化(懒加载,桶个数2^n)
        3. 合理选择初始容量
        4. put方法流程与源码分析
        5. resize源码分析(jdk1.7)
        6. 再哈希rehash和下标(桶)的计算
          1. HashMap中如何存储null key?(table[0])
          2. HashTable和ConcurrentHashMap如何保证不插入null key和value?
          3. 为什么这么设计?(是否支持并发)
        7. 自定义对象作为HashMap的键
        8. 什么情况下性能退化为O(n)(HashMap性能分析)
        9. java8对HashMap的改进
        10. 为什么HashMap是线程不安全的?
        11. 如何线程安全的使用HashMap?
          1. 1、使用Hashtable(不推荐,synchronized)
          2. 2、使用Collections包装(不推荐,synchronized)
          3. 3、使用ConcurrentHashMap(推荐,分段加锁)
          4. 4、自己在代码中访问HashMap时加锁(不推荐,效率低)
      2. WeakHashMap(弱引用版HashMap)
      3. IdentityHashMap(允许key重复)
        1. HashMap中如何插入重复key?(重写equals)
      4. EnumMap
      5. Hashtable(同步的)
        1. Hashtable如何保证线程同步(安全)?
        2. HashTable与HashMap的异同点
      6. LinkedHashMap(按插入排序)
        1. 结点Entry(加before和after指针构成双向链表)
        2. put方法(HashMap的put+重写addEntry)
        3. get方法(重写get方法,增加按访问排序调整)
        4. LinkedHashMap如何实现有序?
        5. 利用LinkedHashMap实现LRU缓存(重写removeEldestEntry)
      7. TreeMap(按key排序)
    4. Collections和Arrays工具类
      1. Arrays.sort(int[] a) 基本类型数组排序(双枢轴快速排序)
      2. Arrays.sort(Object[] a) 对象数组排序(TimSort)
      3. 为什么不同类型采用不同的排序算法?
      4. jdk7/8对Arrays.sort()的优化?
    5. 集合的线程安全
      1. vector,statck,Hashtable,Collections包装都是加synchronized
        1. 并且get方法也都加了synchronized
      2. 通过Collections的同步包装器变成线程安全的
      3. 使用concurrent包的线程安全集合类
    6. 迭代器
      1. Iterator接口
        1. ArrayList的Iterator
        2. ArrayList的ListIterator
        3. 实现Iterable接口的集合可通过foreach语句遍历
        4. 为什么LinkedList用迭代器遍历更快?
      2. Enumeration和Iterator对比
      3. fail-fast快速失败机制
        1. 实现原理
        2. fail-fast解决办法
        3. Hashtable支持fastfail机制吗?
    7. 选择合适的集合类
百度推荐