Java集合类框架面试题

Java集合类框架 HashSet和TreeSet区别

HashSet

TreeSet

TreeSet是SortedSet接口的唯一实现类TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象 linkedHashMap

linkedHashMap的实现就是HashMap+linkedList的实现方式，以HashMap维护数据结构，以linkList的方式维护数据插入顺序

linkedHashMap保存了记录的插入顺序，在用Iterator遍历linkedHashMap时，先得到的记录肯定是先插入的。
在遍历的时候会比HashMap慢TreeMap能够把它保存的记录根据键排序，默认是按升序排序，也可以指定排序的比较器

利用linkedHashMap实现LRU算法缓存（

linkedList首先它是一个Map，Map是基于K-V的，和缓存一致linkedList提供了一个boolean值可以让用户指定是否实现LRU） Java8 中HashMap的优化

（引入红黑树的数据结构和扩容的优化）

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
hashMap 1.8 哈希算法
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

Map遍历的keySet()和entrySet()性能差异原因

Set> entrySet = map.entrySet();
Set set = map.keySet();`

keySet（）循环中通过key获取对应的value的时候又会调用getEntry（）进行循环。循环两次entrySet（）直接使用getEntry（）方法获取结果，循环一次所以 keySet（）的性能会比entrySet（）差点。所以遍历map的话还是用entrySet()来遍历

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

final Entry getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry 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;
        }
        return null;
}

HashMap中的indexFor方法

在HashMap的工作原理，发现它调用了 indexFor(int h, int length) 方法来计算Entry对象保存在 table中的数组索引值：

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

HashMap的初始容量和扩容都是以2的次方来进行的，那么length-1换算成二进制的话肯定所有位都为1，就比如2的3次方为8，length-1的二进制表示就是111，而按位与计算的原则是两位同时为“1”，结果才为“1”，否则为“0”。所以h& (length-1)运算从数值上来讲其实等价于对length取模，也就是h%length。

只有当数组长度为2的n次方时，那么length-1换算成二进制的话肯定所有位都为1,不同的key计算得出的index索引相同的几率才会较小，数据在数组上分布也比较均匀，碰撞的几率也小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

并发的HashMap为什么会引起死循环？

线程不安全的HashMap, HashMap在并发执行put操作时会引起死循环，是因为多线程会导致HashMap的Entry链表形成环形数据结构，查找时会陷入死循环

在扩容resize（）方法中，调用transfer方法，把旧表中的元素添加到新表中，这也是引起死循环的根本原因所在

do {
    Entry next = e.next; // <--假设线程一执行到这里就被调度挂起了
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

执行一：线程A执行到transfer函数中（1）处挂起（transfer函数代码中有标注）。此时在线程A的栈中

e = 3
next = 7

执行二：线程B执行 transfer函数中的while循环，即会把原来的table变成新一table（线程B自己的栈中），再写入到内存,如下图（假设两个元素在新的hash函数下也会映射到同一个位置）

执行三：线程A解挂，接着执行（看到的仍是旧表），即从transfer代码（1）处接着执行，当前的 e = 3, next = 7, 上面已经描述。

处理元素 3 ，将 3 放入线程A自己栈的新table中（新table是处于线程A自己栈中，是线程私有的，不肥线程2的影响

线程A再复制元素 7 ，当前 e = 7 ,而next值由于线程 B 修改了它的引用，所以next 为 3

由于上面取到的next = 3, 接着while循环，即当前处理的结点为3， next就为null ，退出while循环，执行完while循环后

当操作完成，执行查找时，会陷入死循环！

总结：多线程PUT操作时可能会覆盖刚PUT进去的值,扩容操作会让链表形成环形数据结构，形成死循环

ConcurrentHashMap原理

HashTable 在每次同步执行时都要锁住整个结构。ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 将 hash 表分为 16 个桶（默认值）

Java7

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

Java8

Java 8为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N))

Java 8的ConcurrentHashMap同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引。

对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。

HashMap原理 HashMap特性

HashMap的特性：HashMap存储键值对，实现快速存取数据；允许null键/值；非同步；不保证有序(比如插入的顺序)。实现map接口。

HashMap的原理，内部数据结构

HashMap是基于hashing的原理，底层使用哈希表（数组 + 链表）实现。里边最重要的两个方法put、get，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。

存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

HashMap 中 put 方法过程

对key的hashCode做hash操作，然后再计算在bucket中的index（1.5 HashMap的哈希函数）；如果没碰撞直接放到bucket里；如果碰撞了，以链表的形式存在buckets后；如果节点已经存在就替换old value(保证key的唯一性)如果bucket满了(超过阈值，阈值=loadfactor*current capacity，load factor默认0.75)，就要resize。 get()方法的工作原理

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表中查找对应的节点。

HashMap中hash函数怎么是是实现的？还有哪些 hash 的实现方式？

对key的hashCode做hash操作（高16bit不变，低16bit和高16bit做了一个异或）；h & (length-1); //通过位操作得到下标index。

还有数字分析法、平方取中法、分段叠加法、除留余数法、伪随机数法。

HashMap 怎样解决冲突？

HashMap中处理冲突的方法实际就是链地址法，内部数据结构是数组+单链表。

扩展问题1：当两个对象的hashcode相同会发生什么？

因为两个对象的Hashcode相同，所以它们的bucket位置相同，会发生“碰撞”。HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

扩展问题2：抛开 HashMap，hash 冲突有那些解决办法？

开放定址法、链地址法、再哈希法。

如果两个键的hashcode相同，你如何获取值对象？

重点在于理解hashCode()与equals()。

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。两个键的hashcode相同会产生碰撞，则利用key.equals()方法去链表或树（java1.8）中去查找对应的节点。

针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？

将链表转为红黑树，实现 O(logn) 时间复杂度内查找。JDK1.8 已经实现了。

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

扩容。这个过程也叫作rehashing，因为它重建内部数据结构，并调用hash方法找到新的bucket位置。大致分两步：

扩容：容量扩充为原来的两倍（2 * table.length）；移动：对每个节点重新计算哈希值，重新计算每个元素在数组中的位置，将原来的元素移动到新的哈希表中。

补充：

loadFactor。当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍（capacity

为什么String, Interger这样的类适合作为键？

String, Interger这样的类作为HashMap的键是再适合不过了，而且String最为常用。
　　因为String对象是不可变的，而且已经重写了equals()和hashCode()方法了。
　　1.不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。
　　注：String的不可变性可以看这篇文章《【java基础】浅析String》。
　　2.因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

HashMap与HashTable区别

Hashtable可以看做是线程安全版的HashMap，两者几乎“等价”（当然还是有很多不同）。Hashtable几乎在每个方法上都加上synchronized（同步锁），实现线程安全。

区别

HashMap继承于AbstractMap，而Hashtable继承于Dictionary；线程安全不同：Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。而HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理；null值：HashMap的key、value都可以为null。Hashtable的key、value都不可以为null；迭代器(Iterator)：HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException。容量的初始值和增加方式都不一样：HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；添加key-value时的hash值算法不同：HashMap添加元素时，是使用自定义的哈希算法。Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。速度。由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。能否让HashMap同步？

HashMap可以通过下面的语句进行同步：Map m = Collections.synchronizeMap(hashMap);

Collection类

值键值

首先查看jdk中Collection类的源码后会发现如下内容:

public interface Collection extends Iterable {
    // Query Operations

通过查看可以发现Collection是一个接口类，其继承了java迭代接口Iterable。

Java中的类的存储会使用一些容器，链表

大致框架如下:

Collection接口有两个主要的子接口List和Set，注意Map不是Collection的子接口哦这个要牢记。

Collection中可以存储的元素间无序，可以重复组各自独立的元素，即其内的每个位置仅持有一个元素，同时允许有多个null元素对象。

Collection接口中的方法：（源码中有 add等）

List接口

List接口对Collection进行了简单的扩充

查看List接口的源码会发现:

public interface List extends Collection {
    // Query Operations

这里也就知道为什么Collection接口时List接口的父接口了吧。

List接口中的元素的特点为:

List中存储的元素实现类排序，而且可以重复的存储相关元素。

同时List接口又有两个常用的实现类ArrayList和linkedList

1)ArrayList:

ArrayList数组线性表的特点为:类似数组的形式进行存储，因此它的随机访问速度极快。

ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

可以这样理解ArrayList就是基于数组的一个线性表，只不过数组的长度可以动态改变而已。

对于ArrayList的详细使用信息以及创建的过程可以查看jdk中ArrayList的源码，这里不做过多的讲解。

如果在初始化ArrayList的时候没有指定初始化长度的话，默认的长度为10.

ArrayList在增加新元素的时候如果超过了原始的容量的话，ArrayList扩容ensureCapacity的方案为“原始容量*3/2+1"。

public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
    newCapacity = minCapacity;
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
}

ArrayList是线程不安全的，在多线程的情况下不要使用。

如果一定在多线程使用List的，您可以使用Vector，因为Vector和ArrayList基本一致，区别在于Vector中的绝大部分方法都使用了同步关键字修饰，这样在多线程的情况下不会出现并发错误哦，还有就是它们的扩容方案不同，ArrayList是通过原始容量*3/2+1,而Vector是允许设置默认的增长长度，Vector的默认扩容方式为原来的2倍。

切记Vector是ArrayList的多线程的一个替代品。

2)linkedList

linkedList的链式线性表的特点为: 适合于在链表中间需要频繁进行插入和删除操作。

linkedList的链式线性表的缺点为: 随机访问速度较慢。查找一个元素需要从头开始一个一个的找。速度你懂的。

可以这样理解linkedList就是一种双向循环链表的链式线性表，只不过存储的结构使用的是链式表而已。

对于linkedList的详细使用信息以及创建的过程可以查看jdk中linkedList的源码，这里不做过多的讲解。

对于使用linkedList的开发者而言，下面几点内容一定要注意啦，尤其找工作面试的过程时候经常会被问到。

linkedList和ArrayList的区别和联系

ArrayList数组线性表的特点为:类似数组的形式进行存储，因此它的随机访问速度极快。

ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

linkedList的链式线性表的特点为: 适合于在链表中间需要频繁进行插入和删除操作。

linkedList的链式线性表的缺点为: 随机访问速度较慢。查找一个元素需要从头开始一个一个的找。

linkedList的内部实现

对于这个问题，你最好看一下jdk中linkedList的源码。这样你会醍醐灌顶的。

linkedList的内部是基于双向循环链表的结构来实现的。在linkedList中有一个类似于c语言中结构体的Entry内部类。

在Entry的内部类中包含了前一个元素的地址引用和后一个元素的地址引用类似于c语言中指针。

linkedList不是线程安全的

注意linkedList和ArrayList一样也不是线程安全的，如果在对线程下面访问可以自己重写linkedList，然后在需要同步的方法上面加上同步关键字synchronized

linkedList的遍历方法

package com.yonyou.test;

import java.util.linkedList;
import java.util.List;

public class Test{
public static void main(String[] args) {

    List list=new linkedList();
    list.add(“Hello”);
    list.add(“World”);
    list.add(“龙不吟，虎不啸”);
    //linkedList遍历的第一种方式使用数组的方式
    String[] strArray=new String[list.size()];
    list.toArray(strArray);
    for(String str:strArray)
    {
        System.out.println(str);
    }
    //linkedList遍历的第二种方式
    for(String str:list)
    {
        System.out.println(str);
    }
    //至于还是否有其它遍历方式，我没查，感兴趣自己研究研究

}
}
```

linkedList可以被当做堆栈来使用

由于linkedList实现了接口Dueue，所以linkedList可以被当做堆栈来使用

2)Set接口

Set接口也是Collection接口的一个常用子接口。

查看Set接口的源码你会发现：

这里就自然而然的知道Set接口是Collection接口的子接口了吧。

Set接口区别于List接口的特点在于:

Set中的元素实现了不重复，有点象集合的概念，无序，不允许有重复的元素,最多允许有一个null元素对象。

需要注意的是:虽然Set中元素没有顺序，但是元素在set中的位置是有由该元素的HashCode决定的，其具体位置其实是固定的。

查看jdk的源码会发现下面的内容

此外需要说明一点，在set接口中的不重复是由特殊要求的。

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

为了更好的理解，请看下面的例子:

由于String类中重写了hashcode和equals方法，所以这里的第二个Hello是加不进去的哦。

Set接口的常见实现类有HashSet,linkedHashSet和TreeSet这三个。下面我们将分别讲解这三个类。

1)HashSet

HashSet是Set接口的最常见的实现类了。其底层是基于Hash算法进行存储相关元素的。

下面是HashSet的部分源码:

对于HashSet的底层就是基于HashMap来实现的。

我们都知道在HashMap中的key是不允许重复的，你换个角度看看，那不就是说Set集合吗？

这里唯一一个需要处理的就是那个Map的value弄成一个固定值即可。

对于HashMap和Hash算法的讲解会在下面出现，先别着急，下面继续讲解HashSet。

下面讲解一下HashSet使用和理解中容易出现的误区:

a.HashSet中存放null值

HashSet中时允许出入null值的，但是在HashSet中仅仅能够存入一个null值哦。

b.HashSet中存储元素的位置是固定的

HashSet中存储的元素的是无序的，这个没什么好说的，但是由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的哦。

2)linkHashSet

linkHashSet不仅是Set接口的子接口而且还是上面HashSet类的子类。

查看linkedHashSet的部分源码如下:

这里就可以发现Set接口时HashSet接口的一个子接口

通过查看linkedHashSet的源码可以发现,其底层是基于linkedHashMap来实现的。

对于linkedHashSet而言，它和HashSet主要区别在于linkedHashSet中存储的元素是在哈希算法的基础上增加了链式表的结构。

3)TreeSet

TreeSet是一种排序二叉树。存入Set集合中的值，会按照值的大小进行相关的排序操作。底层算法是基于红黑树来实现的。

TreeSet和HashSet的主要区别在于TreeSet中的元素会按照相关的值进行排序~

TreeSet和HashSet的区别和联系

HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key

Map的key和Set都有一个共同的特性就是集合的唯一性.TreeMap更是多了一个排序的功能.

hashCode和equal()是HashMap用的, 因为无需排序所以只需要关注定位和唯一性即可.

算hash值的,hash值是用来确定hash表索引的.

hash表中的一个索引处存放的是一张链表, 所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry.

put时,如果hash表中没定位到,就在链表前加一个Entry,如果定位到了,则更换Entry中的value,并返回旧value

由于TreeMap需要排序,所以需要一个Comparator为键值进行大小比较.当然也是用Comparator定位的.

a. Comparator可以在创建TreeMap时指定

b. 如果创建时没有确定,那么就会使用key.compareTo()方法,这就要求key必须实现Comparable接口.

c. TreeMap是使用Tree数据结构实现的,所以使用compare接口就可以完成定位了.

3)Map接口

四个常用的实现类，分别是HashMap、Hashtable、linkedHashMap和TreeMap

Map接口实现的是一组Key-Value的键值对的组合。 Map中的每个成员方法由一个关键字（key）和一个值（value）构成。Map接口不直接继承于Collection接口（需要注意），因为它包装的是一组成对的“键-值”对象的集合，而且在Map接口的集合中也不能有重复的key出现，因为每个键只能与一个成员元素相对应。在我们的日常的开发项目中，我们无时无刻不在使用者Map接口及其实现类。Map有两种比较常用的实现：HashMap和TreeMap等。HashMap也用到了哈希码的算法，以便快速查找一个键，TreeMap则是对键按序存放，因此它便有一些扩展的方法，比如firstKey(),lastKey()等，你还可以从TreeMap中指定一个范围以取得其子Map。键和值的关联很简单，用pub(Object key,Object value)方法即可将一个键与一个值对象相关联。用get(Object key)可得到与此key对象所对应的值对象。

另外，Set接口的底层是基于Map接口实现的。Set中存储的值，其实就是Map中的key，它们都是不允许重复的。Map接口的常见实现类HashMap、TreeMap、linkedHashMap、Properties(继承HashTable)以及老版本的HashTable等。

HashMap

HashMap实现了Map、CloneMap、Serializable三个接口，并且继承自AbstractMap类。

HashMap基于hash数组实现，若key的hash值相同则使用链表方式进行保存。

新建一个HashMap时,默认的话会初始化一个大小为16，负载因子为0.75的空的HashMap

下面是一个HashMap中还存在一个内部类Entry，用于链表的存储

源代码其实告诉我们Entry是一个结点，它持有下一个元素的引用，这样就构成了一个链表。

那么，整体上来说HashMap底层就是使用这样一个数据结构来实现的。

我们提到使用Hash，但是Hash值如何与元素的存储建立关系呢？（Hash算法）

在数据结构课中我们学习过Hash的简单算法，就是给你一个Hash因子，通过对该元素的hashCode简单的求余，来实现对其快速的定位和索引。

在HashMap中有这样的代码：

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

这个方法在HashMap中非常重要，凡是与查询、添加、删除有关的方法中都有调用该方法，为什么这么短的一个代码使用率这么高？根据代码注释我们知道，这个方法是根据hashCode及当前table的长度（数组的长度，不是map的size）得到该元素应该存放的位置，或者在table中的索引。

现在我们需要看一下当数据量已经超过初始定义的负载因子时，HashMap如何处理？

在HashMap中当数据量很多时，并且已经达到了负载限度时，会重新做一次哈希，也就是说会再散列。调用的方法为resize()，并且java默认传入的参数为2*table.length。

这里就产生了一个很重要的问题，那就是怎么让哈希表的分布比较均匀，也就是说怎么让它即不会成为一个单链表（极限情况，每个key的hash值都集中到了一起），又不会使hash空间过大（导致内存浪费）？

上面两个问题一个是解决了怎么计算hash值快速存取，一个是怎么实现再哈希，何时需要再哈希。快速存取的前提是元素分布均匀，不至于集中到一点，再哈希是元素过于零散，导致不断的重新构建表。

那么在第一个问题中我们看到了这样一个代码****return**** h & (length-1);在第二个问题中我们说过内部调用传入的值为2*table.length;并且默认情况下HashMap的大小为一个16的数字，除了默认构造提供大小为16的空间外，如果我们使用

public HashMap(int initialCapacity, float loadFactor)

上面的构造方法，我们会发现这样的代码：

也就是说当我们传入1000时，它并没有给我们构造一个容量为1000的哈希表，而是构建了一个容量为1024大小的哈希表。

从整体上我们发现一个问题，那就是无论什么情况HashMap中哈希表的容量总是2的n次方的一个数。并且有这样一个公式：

当length=2^n时，hashcode & (length-1) == hashcode % length

也就是这一点验证了第一个问题，hash索引值的计算方法其实就是对哈希因子求余。只有大小为2的n次方时，那样的计算才成立，所以HashMap为我们维护了一个这样大小的一个哈希表。（位运算速度比取模运算快的多）

c) HashMap的使用方法：

我在很多代码中都用到了HashMap，原因是首先它符合存储关联数据的要求，其次它的存取速度快，这是一个选择的问题。

linkedHashMap的特点、实现机制及使用方法

a) linkedHashMap的特点：

linkedHashMap继承自HashMap并且实现了Map接口。和HashMap一样，linkedHashMap允许key和value均为null。

于该数据结构和HashMap一样使用到hash算法，因此它不能保证映射的顺序，尤其是不能保证顺序持久不变（再哈希）。

如果你想在多线程中使用，那么需要使用Collections.synchronizedMap方法进行外部同步。

linkedHashMap与HashMap的不同之处在于，linkedHashMap维护者运行于所有条目的双重链接列表，此链接列表可以是插入顺序或者访问顺序。

b) linkedHashMap的实现机制：

无法总结下去，在网上看到这样一篇文章：http://zhangshixi.iteye.com/blog/673789

感觉真的没办法总结下去了。

HashMap与Hashtable的区别：

Hashtable实现Map接口，继承自古老的Dictionary类，实现一个key-value的键值映射表。任何非空的（key-value）均可以放入其中。

区别主要有三点：

Hashtable是基于陈旧的Dictionary实现的，而HashMap是基于Java1.2引进的Map接口实现的；

Hashtable是线程安全的，而HashMap是非线程安全的，我们可以使用外部同步的方法解决这个问题。

HashMap可以允许你在列表中放一个key值为null的元素，并且可以有任意多value为null，而Hashtable不允许键或者值为null。

WeakHashMap的特点：

我没有使用过这个类。网摘：WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。(后续使用后进行总结)

下面针对各个实现类的特点做一些说明：

(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

(3) linkedHashMap：linkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历linkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。

深入讲解：https://tech.meituan.com/2016/06/24/java-hashmap.html

Map和ConcurrentHashMap的区别？

HashTable

· 底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化

· 初始size为11，扩容：newsize = olesize*2+1

· 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

· 底层数组+链表实现，可以存储null键和null值，线程不安全

· 初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂

· 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入

· 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）

· 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀

· 计算index方法：index = hash & (tab.length – 1)

ConcurrentHashMap

底层采用分段的数组+链表实现，线程安全通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

https://tech.meituan.com/2016/06/24/java-hashmap.html

Java集合类框架面试题

Java相关栏目本月热门文章