lindamao

lindamao

集合

发布于 2020-04-14 | 30分钟 | 7729字数

List,Set,Map三者的区别

List (对付顺序的好帮⼿)： 存储的元素是有序的、可重复的。

Set (注重独⼀⽆⼆的性质): 存储的元素是⽆序的、不可重复的

Map (⽤ Key 来搜索的专家): 使⽤键值对（kye-value）存储，类似于数学上的函数y=f(x)，“x”代表 key，"y"代表 value，Key 是⽆序的、不可重复的，value 是⽆序的、可重复的，每个键最多映射到⼀个值。
do1kr.png

List

CopyOnWriteArrayList

读写分离list

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。

写操作需要加锁，防止并发写入时导致写入数据丢失。 写操作结束之后需要把原始数组指向新的复制数组

适用于读多写少的场景

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

Arraylist 与 LinkedList 区别?

  1. 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

  2. 底层数据结构： Arraylist 底层使⽤的是 Object 数组； LinkedList 底层使⽤的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别）

  3. 插⼊和删除是否受元素位置的影响：

    ① ArrayList 采⽤数组存储，所以插⼊和删除元素的时间复杂度受元素位置的影响。 ⽐如：执⾏ add(E e) ⽅法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i插⼊和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进⾏上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执⾏向后位/向前移⼀位的操作。

    ②
    LinkedList 采⽤链表存储，所以对于 add(E e) ⽅法的插⼊，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置 i 插⼊和删除元素的话（ (add(int index, Eelement) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊。

    arraylist实现了randomaccess接口 但是linked没有。

  4. 是否⽀持快速随机访问： LinkedList 不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index)**** ⽅法)

  5. 内存空间占⽤： ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留⼀定的容量空间预留给将要插入的元素 ⽽ LinkedList 的空间花费则体现在它的每⼀**个元素都需要消耗⽐ ArrayList 更多的空间（**因为要存放直接后继和直接前驱以及数据）。

Arraylist 与 LinkedList的有些成员变量为什么使用transient关键字

1.ArrayList中将elementData修饰成transient是为了节省空间

2.LinkedList中将first和last修饰成transient是为了节省空间和重新连接链表。

Arraylist源码分析

https://baijiahao.baidu.com/s?id=1637926321175819771&wfr=spider&for=pc

Arraylist为什么用1.5倍扩容

k=1.5时，就能充分利用前面已经释放的空间。如果k >= 2，新容量刚刚好永远大于过去所有废弃的数组容量会造成空间利用资源的浪费

  • 为什么不取扩容固定容量呢？
    扩容的目的需要综合考虑这两种情况：
  1. 扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制
  2. 扩容容量不能太大，需要充分利用空间，避免浪费过多空间；

而扩容固定容量，很难决定到底取多少值合适，取任何具体值都不太合适，因为所需数据量往往由数组的客户端在具体应用场景决定。依赖于当前已经使用的量 * 系数， 比较符合实际应用场景。比如，我现在已经用到一个数组100的容量，接下来很可能会有这个数量级的数据需要插入。

  • 为什么是1.5，而不是1.2，1.25，1.8或者1.75？
    因为1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数 提示计算的效率。

双向链表和双向循环链表

双向链表： 包含两个指针，⼀个 prev 指向前⼀个节点，⼀个 next 指向后⼀个节点

do7pM.png

ArrayList 与 Vector 区别呢?为什么要⽤Arraylist取代Vector呢？

  • ArrayList 是 List 的主要实现类，底层使⽤ Object[ ] 存储，适⽤于频繁的查找⼯作，线程不安全 ；
  • Vector 是 List 的古⽼实现类，底层使⽤ Object[ ] 存储，线程安全的。

ArrayList 的扩容机制

概括的说，ArrayList 是一个动态数组，它是线程不安全的，允许元素为null。其底层数据结构依然是数组，它实现了List, RandomAccess, Cloneable, java.io.Serializable接口，其中RandomAccess代表了其拥有随机快速访问的能力，ArrayList可以以**O(1)**的时间复杂度去根据下标访问元素。

因其底层数据结构是数组，所以可想而知，它是占据一块连续的内存空间（容量就是数组的length），所以它也有数组的缺点，空间效率不高。

由于数组的内存连续，可以根据下标以O(1)的时间读写(改查)元素，因此时间效率很高。

当集合中的元素超出这个容量，便会进行扩容操作。扩容操作也是ArrayList 的一个性能消耗比较大的地方，所以若我们可以提前预知数据的规模，应该通过public ArrayList(int initialCapacity) {}构造方法，指定集合的大小，去构建ArrayList实例，以减少扩容次数，提高效率。

或者在需要扩容的时候，手动调用public void ensureCapacity(int minCapacity) {}方法扩容。不过该方法是ArrayList的API，不是List接口里的，所以使用时需要强转:

((ArrayList)list).ensureCapacity(30);

当每次修改结构时，增加导致扩容，或者删，都会修改modCount。

先点进源码查看

构造方法：
//存储集合元素的底层实现：真正存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
//当前元素数量
private int size;

//默认构造方法
public ArrayList() {
    //默认构造方法只是简单的将 空数组赋值给了elementData
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//带初始容量的构造方法
//如果传入参数，则代表指定ArrayList的初始数组长度，传入参数如果是大于等于0，则使用用户的参数初始化，如果用户传入的参数小于0，则抛出异常，构造方法如下： 
public ArrayList(int initialCapacity) {
    //如果初始容量大于0，则新建一个长度为initialCapacity的Object数组.
    //注意这里并没有修改size(对比第三个构造函数)
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {//如果容量为0，直接将EMPTY_ELEMENTDATA赋值给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {//容量小于0，直接抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

//利用别的集合类来构建ArrayList的构造函数
public ArrayList(Collection<? extends E> c) {
    //直接利用Collection.toArray()方法得到一个对象数组，并赋值给elementData 
    elementData = c.toArray();
    //因为size代表的是集合元素数量，所以通过别的集合来构造ArrayList时，要给size赋值
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)//这里是当c.toArray出错，没有返回Object[]时，利用Arrays.copyOf 来复制集合c中的元素到elementData数组中
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果集合c元素数量为0，则将空数组EMPTY_ELEMENTDATA赋值给elementData 
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
参数
	// 序列化id
	private static final long serialVersionUID = 8683452581122892189L;
	// 默认初始的容量
	private static final int DEFAULT_CAPACITY = 10;
	// 一个空对象
	private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
	// 一个空对象，如果使用默认构造函数创建，则默认对象内容默认是该值
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
	// 当前数据对象存放地方，当前对象不参与序列化
	transient Object[] elementData;
	// 当前数组长度
	private int size;
	// 数组最大长度
	private static final int MAX_ARRAY_SIZE = 2147483639;


//这是一个空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

这段源码说明当你没有向集合中添加任何元素时，集合容量为0。那么默认的10个容量怎么来的呢？

这就得看看add方法的源码了：

这里大家要注意一下Collection.toArray()这个方法，在Collection子类各大集合的源码中，高频使用了这个方法去获得某Collection的所有元素。

关于方法：Arrays.copyOf(elementData, size, Object[].class)，就是根据class的类型来决定是new 还是反射去构造一个泛型数组，同时利用native函数，批量赋值元素至新数组中。
如下：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    //根据class的类型来决定是new 还是反射去构造一个泛型数组
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //利用native函数，批量赋值元素至新数组中。
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

值得注意的是，System.arraycopy也是一个很高频的函数，大家要留意一下。

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
常用API：

1.增

add的方法有两个，一个是带一个参数的，一个是带两个参数的。
add(E e) 方法

add主要的执行逻辑如下：
1）确保数组已使用长度（size）加1之后足够存下 下一个数据
2）修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组。

grow方法会将当前数组的长度变为原来容量的1.5倍。
3）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
4）返回添加成功布尔值。

添加元素方法入口：

    public boolean add(E e) {
        //扩容的操作 当容量不够的时候就把容量扩大
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //想数组中添加元素
        elementData[size++] = e;
        return true;
    }

确保添加的元素有地方存储，当第一次添加元素的时候this.size+1 的值是1，所以第一次添加的时候会将当前elementData数组的长度变为10：

//最初的数组容量为0     
private void ensureCapacityInternal(int minCapacity) {
		//第一次判断数组当中为空 默认的数组的数组也是空 所以第一次添加条件成立
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           	//max函数比较当前容量和默认容量 当前为0 默认为10 所以返回大的是10 所以第一次添加完成之后就变成了10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    //扩容完成执行下面的操作
        ensureExplicitCapacity(minCapacity);
    }

将修改次数（modCount）自增1，判断是否需要扩充数组长度,判断条件就是用当前所需的数组最小长度与数组的长度对比，如果大于0，则增长数组长度。

//当前容量为10private void ensureExplicitCapacity(int minCapacity) {    	//修改次数+1        modCount++;        // overflow-conscious code    	//当前容量为哦10 减去数组的长度0大于0        if (minCapacity - elementData.length > 0)            //执行扩容操作            grow(minCapacity);    }

如果当前的数组已使用空间（size）加1之后 大于数组长度，则增大数组容量，扩大为原来的1.5倍。

//此时的minCapacity为10private void grow(int minCapacity) {        // overflow-conscious code    	//旧的容量为当前数组的长度为0        int oldCapacity = elementData.length;    	//扩容操作    	//新的长度为旧的加上旧的右移1位 0+0还是0    	//假设此时的数组的长度已经到达10 的时候 就会变成15        int newCapacity = oldCapacity + (oldCapacity >> 1);    	//判断最新的容量是否大于之前的最小容量 目的是让最新的容量要大于等于之前的最小容量        if (newCapacity - minCapacity < 0)                    newCapacity = minCapacity;        if (newCapacity - MAX_ARRAY_SIZE > 0)            //MAX_ARRAY_SIZE是个超级大的数字 如果数组不是很大的话是下面的条件一般是不会成立的            newCapacity = hugeCapacity(minCapacity);        // minCapacity is usually close to size, so this is a win:    	//第一次创建数组 此时的数组长度为newCapacity的大小     	//后面也是如此        elementData = Arrays.copyOf(elementData, newCapacity);    }

add(int index, E element)方法

这个方法其实和上面的add类似，该方法可以按照元素的位置，指定位置插入元素，具体的执行逻辑如下：
1）rangeCheckForAdd(index)确保数插入的位置小于等于当前数组长度，并且不小于0，否则抛出异常

2）确保数组已使用长度（size）加1之后足够存下 下一个数据

3）修改次数（modCount）标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组

4）grow方法会将当前数组的长度变为原来容量的1.5倍。

5）确保有足够的容量之后，使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位。

6）将新的数据内容存放到数组的指定位置（index）上

 public void add(int index, E element) {        rangeCheckForAdd(index);        ensureCapacityInternal(size + 1);  // Increments modCount!!     	//通过数组复制的方式复制一次数组        System.arraycopy(elementData, index, elementData, index + 1,                         size - index);        elementData[index] = element;        size++;    }

注意：使用该方法的话将导致指定位置后面的数组元素全部重新移动，即往后移动一位。

总结：
add、addAll。
先判断是否越界，是否需要扩容。
如果扩容， 就复制数组。
然后设置对应下标元素值。

值得注意的是：
1 如果需要扩容的话，默认扩容一半。如果扩容一半不够，就用目标的size作为扩容后的容量。
2 在扩容成功后，会修改modCount

Map Set

HashMap 和 Hashtable 的区别

  1. 线程是否安全： HashMap 是⾮线程安全的， HashTable 是线程安全的,因为 HashTable 内部的⽅法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使⽤ConcurrentHashMap 吧！）；

  2. 效率： 因为线程安全的问题， HashMap 要⽐ HashTable 效率⾼⼀点。另外， HashTable基本被淘汰，不要在代码中使⽤它；

  3. 对 Null key 和 Null value 的⽀持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有⼀个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出NullPointerException 。

  4. 初始容量⼤⼩和每次扩充容量⼤⼩的不同 ：

① 创建时如果不指定容量初始值， Hashtable默认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1。 HashMap 默认的初始化⼤⼩为 16。之后每次扩充，容量变为原来的 2 倍。

② 创建时如果给定了容量初始值，那么Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为 2 的幂次⽅⼤⼩（ HashMap 中的 tableSizeFor() ⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤ 2 的幂作为哈希表的⼤⼩,后⾯会介绍到为什么是 2 的幂次⽅。

  1. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间Hashtable 没有这样的

1、继承：
HashTable继承自Dirctionary，HashMap继承自AbstractMap，二者均实现了Map接口；
2、线程安全性：
HashTable的方法是同步的，即是线程安全的。HaspMap的方法不是同步的，不是线程安全的的。在多线程并发的情况下，我们可以直接使用HashTable，如果 要使用HashMap，就需要自行对HashMap的同步处理。
3、键值：
HashTable中不允许有null键和null值，HashMap中允许出现一个null键，可以存在一个或者多个键的值都为null。程序中，对HashMap，如果使用get(参数为 键)方法时，返回结果为null，可能是该键不存在，也可能是该键对应的值为null，这就出现了结果的二义性。因此，在HashMap中，我们不能使用get()方法来查询键 对应的值，应该使用containskey()方法。
4、遍历：
这两个在遍历方式的实现不同。HashTable和HashMap两者都实现了Iterator。但是，由于历史原因，HashTable还使用Enumeration。
5、哈希值：
HashTable是直接使用对象的hashCode。HashMap是重新计算hash值。
6、扩容：
HashTable和HashMap的底层实现的数组和初始大小和扩容方式。HashTable初始大小为11，并且每次扩容都为：2old+1。HashMap的默认大小为16，并且一 定是2的指数，每次扩容都为old2。

HashMap 和 HashSet区别

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

因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外，其他⽅法都是直接调⽤ HashMap 中的⽅法。
doNYG.png

HashSet当中为什么要对HashMap使用transient关键字

在源码当中查看 其实HashSet当中还有这两个方法

private void writeObject(java.io.ObjectOutputStream s){}

private void readObject(java.io.ObjectInputStream s){}

分析得出结论：

在序列化HashSet的时候，会调HashSet中的writeObject，将hashSet中的hashMap中的数据序列化存起来，而在反序列化的时候，会调用Hashset中的readObject来重新构造hashSet中的hashMap，这样的话，就完全没必要序列化hashSet中的HashMap

反射调用HashSet的writeObject方法，同理反序列化也就是在反射调用HashSet中的readObjcet方法

HashSet如何检查重复

当你把对象加⼊ HashSet 时， HashSet 会先计算对象的 hashcode 值来判断对象加⼊的位置，同时也会与其他加⼊的对象的 hashcode 值作比较，如果没有相符的 hashcode ，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调⽤ equals() ⽅法来检查hashcode 相等的对象是否真的相同。如果两者相同， HashSet 就不会让加⼊操作成功。

HashMap的底层实现

JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在⼀起使⽤也就是 链表散列。HashMap 通过key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这⾥的 n 指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash ⽅法。使⽤ hash ⽅法也就是扰动函数是为了防⽌⼀些实现⽐较差的 hashCode() ⽅法 换句话说使⽤扰动函数之后可以减少

相⽐于 JDK1.8 的 hash ⽅法 ，JDK 1.7 的 hash ⽅法的性能会稍差⼀点点，因为毕竟扰动了 4次。所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8 之后
相⽐于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链表转化为红⿊树，以减少搜索时间

HashMap 多线程操作导致死循环问题

主要原因在于 并发下的Rehash 会造成元素之间会形成⼀个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使⽤ HashMap,因为多线程下使⽤ HashMap 还是会存在其他问题⽐如数据丢失。并发环境下推荐使⽤ ConcurrentHashMap 。

  • 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) {                //重新计算hash值                e.hash = null == e.key ? 0 : hash(e.key);            }            //这里根据刚刚得到的新hash重新调用indexFor方法计算下标索引            int i = indexFor(e.hash, newCapacity);            //假设当前数组中某个位置的链表结构为a->b->c;women             //（1）当为原链表中的第一个结点的时候：e.next=null;newTable[i]=e;e=e.next            //（2）当遍历到原链表中的后续节点的时候：e.next=head;newTable[i]=e（这里将头节点设置为新插入的结点，即头插法）;e=e.next            //（3）这里也是导致扩容后，链表顺序反转的原理（代码就是这样写的，链表反转，当然前提是计算的新下标还是相同的）            e.next = newTable[i];             newTable[i] = e;            e = next;        }    }}

    在jdk7中使用头插法可能会导致出现死环（a.next = b，b.next = a）。导致在put的时候一直获取不到数据。

    • 两个线程同时对一个hashMap resize。线程a执行到Entry<K,V> next = e.next;被阻塞了，线程b执行完了resize，此时a再继续执行时，可能会导致死环。

详情请查看：https://coolshell.cn/articles/9606.html

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。

底层数据结构： JDK1.7 的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8采⽤的数据结构跟 HashMap1.8 的结构⼀样，数组+链表/红⿊⼆叉树。 Hashtable 和JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；

实现线程安全的⽅式（重要）：

① 在 JDK1.7 的时候， ConcurrentHashMap （分段锁）对整个桶数组进⾏了分割分段( Segment )，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤ synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap ，虽然在 JDK1.8 中还能看到Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；

② Hashtable (同⼀把锁) :使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈效率越低。

两者的对⽐图：
HashTable

do3lM.png

JDK1.7 的 ConcurrentHashMap：

dowBG.png

JDK1.8 的 ConcurrentHashMap：

JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，⽽是 Node 数组 + 链表 / 红⿊树。不过，Node 只能⽤于链表的情况，红⿊树的情况需要使⽤ TreeNode 。当冲突链表达到⼀定⻓度时，链表会转换成红⿊树。

ConcurrentHashMap线程安全的具体实现⽅式/底层具体实现

JDK1.7
⾸先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程占⽤锁访问其中⼀个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock ,所以 Segment 是⼀种可重⼊锁，扮演锁的⻆⾊。 HashEntry 用于储存键值对数据

dqMZ1.png

⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数组。 Segment 的结构和 HashMap 类似，是⼀种数组和链表结构，⼀个 Segment 包含⼀个 HashEntry 数组，每个 HashEntry 是⼀个链表结构的元素，每个 Segment 守护着⼀个 HashEntry 数组⾥的元素，当对 HashEntry 数组的数据进⾏修改时，必须⾸先获得对应的 Segment 的锁。

JDK1.8
ConcurrentHashMap 取消了 Segment 分段锁，采⽤ CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类

似，数组+链表/红⿊⼆叉树。Java 8 在链表⻓度超过⼀定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红⿊树（寻址时间复杂度为 O(log(N))）
synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要 hash 不冲突，就不会产⽣并发，效率⼜提升 N 倍。

⽐较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet 是 Set 接⼝的主要实现类 ， HashSet 的底层是 HashMap ，线程不安全的，可以存储 null 值； 无序
LinkedHashSet 是 HashSet 的⼦类，能够按照添加的顺序遍历；有序
TreeSet 底层使⽤红⿊树，能够按照添加元素的顺序进⾏遍历，排序的⽅式有⾃然排序和定制排序 。有序

HashMap的扩容为什么要选用2倍

当HashMap的容量达到threshold域值时，就会触发扩容。扩容前后，哈希桶的长度一定会是2的次方。这样在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效。

  • capacity 为 2的整数次幂的话，计算桶的位置 h&(length-1) 就相当于对 length 取模，提升了计算效率
  • capacity 为 2 的整数次幂的话，便保证了 h&(capacity-1) 的结果可能是0也可能是1，保证了散列的均匀性
  • capacity 为 2 的整数次幂可以使得在resize的时候不用重新计算hash值。而通过(e.hash & oldCap) == 0 ? 原来位置 : 原来位置+原来哈希表大小就能算出在新哈希表的正确位置（能通过(n - 1) & hash正确获取元素）

HashMap的负载因子为什么为0.75

负载因子，默认值是0.75。负载因子表示一个散列表的空间的使用程度，有这样一个公式：initailCapacity*loadFactor=HashMap的容量。 所以负载因子越大则散列表的装填程度越高，也就是能容纳更多的元素，元素多了，链表大了，所以此时索引效率就会降低。反之，负载因子越小则链表中的数据量就越稀疏，此时会对空间造成烂费，但是此时索引效率高。

当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。

HashMap的遍历方式

https://www.cnblogs.com/xyfer1018/p/10434827.html

  • 第一种：遍历HashMap的entrySet键值对集合

    • 1.通过**HashMap.entrySet()**得到键值对集合；

      2.通过迭代器Iterator遍历键值对集合得到key值和value值；

      Iterator it = map.entrySet().iterator();

  • 第二种：遍历HashMap键的Set集合获取值；

    1.通过HashMap.keySet()获得键的Set集合；

    2.遍历键的Set集合获取值；

    Iterator it = map.keySet().iterator();

  • 第三种：遍历HashMap“值”的集合；

    1.通过HashMap.values()得到“值”的集合

    2.遍历“值”的集合；

    Iterator it = map.values().iterator();

如何用一个数组构造hashmap

hashmap的底层是通过数组+链表+红黑树的形式

关键是构造entry数组

dqO0I.png

https://blog.csdn.net/miracleon/article/details/102542395

解决hash冲突的方法

https://www.cnblogs.com/kaleidoscope/p/9588151.html

  • 拉链法

  • 散列法（开放地址法）

    • 所有输入的元素全部存放在哈希表里，也就是说，位桶的实现是不需要任何的链表来实现的，换句话说，也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。
    • 缺点：每次冲突都要重新散列，计算时间增加。

hash表相关考点

解决哈希冲突的链地址算法 插入新数据项的时间表述中 随装载因子线性增长

哈希表的装填因子

装填因子 = （哈希表中的记录数） / （哈希表的长度）。

装填因子是哈希表装满程度的标记因子。值越大，填入表中的数据元素越多，产生冲突的可能性越大。

集合框架底层数据结构总结

List

  • Arraylist ： Object[] 数组
  • Vector ： Object[] 数组
  • LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set

  • Arraylist ： Object[] 数组
  • Vector ： Object[] 数组
  • LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Map

  • HashMap ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较 ⼤的变化，当链表⻓度⼤于阈值（默认为 8）（将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树）时，将链转化为红⿊树，以减少搜索时间
  • LinkedHashMap ： LinkedHashMap 继承⾃ HashMap ，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红⿊树组成。另外， LinkedHashMap 在上⾯结构的基础上，增加了⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
  • Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的
  • TreeMap ： 红⿊树（⾃平衡的排序⼆叉树）

如何选⽤集合

主要根据集合的特点来选⽤，⽐如我们需要根据键值获取到元素值时就选⽤ Map 接⼝下的集合，需要排序时选择 TreeMap ,不需要排序时就选择 HashMap ,需要保证线程安全就选⽤ConcurrentHashMap 。

当我们只需要存放元素值时，就选择实现 Collection 接⼝的集合，需要保证元素唯⼀时选择实现Set 接⼝的集合⽐如 TreeSet 或 HashSet ，不需要就选择实现 List 接⼝的⽐如 ArrayList 或LinkedList ，然后再根据实现这些接⼝的集合的特点来选⽤。

线程同步的集合

线程同步：喂，SHE

喂（Vector）

S（Stack）

H（hashtable）

E（enumeration）

基本算法 上一篇
JAVA基础 下一篇
已运行:
浏览数: 次 | 访客数: 人
0%