目录
6."如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
集合：
集合的框架：
* |----Collection接口：单列集合，用来存储一个一个的对象
* |----List接口：存储有序的、可重复的数据。 -->“动态”数组
* |----ArrayList、LinkedList、Vector
*
* |----Set接口：存储无序的、不可重复的数据
* |----HashSet、LinkedHashSet、TreeSet
*
* |----Map接口：双列集合，用来存储一对(key - value)一对的数据
* |----HashMap、LinkedHashMap、TreeMap、Hashtable、Properties
一、List
List 是有序的 Collection
List中的元素是有序的、可重复的，主要实现方式有动态数组和链表。
java中提供的List的实现主要有ArrayList、LinkedList、CopyOnWriteArrayList，另外还有两个古老的类Vector和Stack。
1.ArrayList
ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable等接口。
ArrayList实现了List，提供了基础的添加、删除、遍历等操作。
ArrayList实现了RandomAccess，提供了随机访问的能力。
ArrayList实现了Cloneable，可以被克隆。
ArrayList实现了Serializable，可以被序列化。
AbstractCollection：主要实现了toString()、toArray()、contains()
AbstractList：主要实现了equals()、hashCode()
缺点：
①数组长度固定，java里面数组都是定长数组，比如数组大小设置为100，此时你不停的往ArrayList里面塞入这个数据，此时元素数量超过了100以后，此时就会发生一个数组的扩容，就会搞一个更大的数组，把以前的数组拷贝到新的数组里面去，这个数组扩容+元素拷贝的过程，相对来说会慢一些
②中间插入慢，数组来实现，数组你要是往数组的中间加一个元素，要把数组中那个新增元素后面的元素全部往后面挪动一位，所以说，如果你是往ArrayList中间插入一个元素，性能比较差，会导致他后面的大量的元素挪动一个位置
优点：
①支持随机访问，通过索引访问元素极快，时间复杂度为O(1)
2.LinkedList
LinkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用
因为ArrayList代表了List的典型实现，LInkedList代表了Deque的典型实现，同时LinkedList也实现了List，通过这两个类一首一尾正好可以把整个集合贯穿起来。
优点：
①插入性能高，不管是从末尾插入还是中间插入
缺点：
随机读性能差，例如LinkedList.get(10)，这种操作，性能就很低，因为他需要遍历这个链表，从头开始遍历这个链表，直到找到index = 10的这个元素为止
使用场景
（1）ArrayList：一般场景，都是用ArrayList来代表一个集合，只要别频繁的往里面插入和灌入大量的元素就可以了，遍历，或者随机查，都可以
（2）LinkedList：适合，频繁的在list中插入和删除某个元素，然后尤其是LinkedList他其实是可以当做队列来用的，这个东西的话呢，我们后面看源码的时候，可以来看一下，先进先出，在list尾部怼进去一个元素，从头部拿出来一个元素。如果要在内存里实现一个基本的队列的话，可以用LinkedList
3.Vector&Stack
栈由Vector和Stack两个来实现，Stack代表了一个栈这种数据结构，他是继承自Vector来实现的，Vector是一种类似于ArrayList（基于数组来实现的）数据结构，有序的集合，Stack是一种基于数组来实现的栈数据结构
栈，先进后出，跟队列的先进先出是不一样
队列：一般是队尾巴进去开始排队，从队头开始出来，排队的过程，先进先出
栈：进去的时候直接压入栈底，出来的时候是从栈的最上面一个元素开始先出来，先进后出
ArrayList每次扩容是1.5倍，capacity + (capacity >> 1) = 1.5
Vector每次扩容默认是2倍，默认情况下是直接扩容两倍，2倍
————————————————
原文链接：https://blog.csdn.net/qq_35620342/article/details/119947254
二、Set
1.HashSet
比如说HashSet就是基于HashMap来实现的
HashSet，他其实就是说一个集合，里面的元素是无序的，他里面的元素不能重复的，HashMap的key是无顺序的，你插入进去的顺序，跟你迭代遍历的顺序是不一样的，而且HashMap的key是没有重复的，HashSet可以直接基于HashMap来实现
2.LinkedHashSet
LinkedHashSet，他是有顺序的set，也就是维持了插入set的这个顺序，你迭代LinkedHashSet的顺序跟你插入的顺序是一样的，底层直接就可以基于LinkedHashMap来实现
3.TreeSet
TreeSet，默认是根据你插入进去的元素的值来排序的，而且可以定制Comparator，自己决定排序的算法和逻辑，他底层可以基于TreeMap来实现
Set底层的Map，只有key是有值的，value都是null值，都是空的
————————————————
原文链接：https://blog.csdn.net/qq_35620342/article/details/119947254
三、Map
1.谈一下HashMap的特性？
- 1.HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
- 2.非同步，线程不安全。
- 3.底层是hash表，不保证有序(比如插入的顺序)
2.谈一下HashMap的底层原理是什么？
- JDK1.7的是数组+链表
（1.7只是一个例子，以前的话也是这样后面就以1.7为例子了）
首先是一个数组，然后数组的类型是链表
元素是头插法
- JDK1.8的是数组+链表 或者 数组+红黑树
首先是一个数组，然后数组的类型是链表，在链表的元素大于8的时候，会变成红黑树，在红黑树的元素小于6的时候会变成链表
元素进行尾插
- HaspMap的数组默认大小为16，扩容机制：2倍数组扩容
- HashMap线程不安全
在put的时候，Resize（扩容）会造成数据的覆盖
JDK1.7 因为是头插法，可能会造成循环链表
JDK1.8 是尾插法
3.jdk1.8中对HaspMap做了哪些优化？
- 数组+链表改成了数组+链表或红黑树
- 链表的插入方式从头插法改成了尾插法
- 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
- 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；
4.谈一下当两个对象的hashCode相等时会怎么样？
- 会产生哈希碰撞，若key值相同则替换旧值，不然链接到链表后面，链表长度超过阙值8就转为红黑树存储
5.如果两个键的hashcode相同，你如何获取值对象？
- HashCode相同，通过equals比较内容获取值对象
6."如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
- 超过阙值会进行扩容操作，概括的讲就是扩容后的数组大小是原数组的2倍，将原来的元素重新hashing放入到新的散列表中去。
7.HashMap和HashTable的区别
相同点：都是存储key-value键值对的
不同点：
-
HashMap允许Key-value为null，hashTable不允许；
-
hashMap没有考虑同步，是线程不安全的。hashTable是线程安全的，给api套上了一层synchronized修饰;
-
HashMap继承于AbstractMap类，hashTable继承于Dictionary类。
-
迭代器(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()。
8.HashMap为什么线程不安全？
HashMap 在并发执行 put 操作时会引起死循环，导致 CPU 利用率接近100%。
两个方法，两个并发线程同时put元素，如果根据key值计算的hash值一样，那么put的数据会被覆盖；如果两个线程同时检测到当前数组大小大于容量*loadactory之后，会同时扩容并重新计算元素的新位置，并更新数组，这样最后就会出现有一个线程的数据会丢失。HashMap在线程并发时会容易死循环，死循环不是发生在put时而发生在扩容时。
1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
9.如何让HashMap线程安全？
- 使用ConcurrentHashMap，简称CHM
CHM是在JDK1.5之后引入的，用来替代HashTable，是concurrent包的重要成员，在JDK1.5之前如果要保证线程安全的使用map，只能选择HashTable或者SynchronizedMap，但是在操作map时，HashTable和SynchronizedMap会锁住整个map，引入了ConcurrentHashMap之后，在操作map时，只锁住了部分，允许多线程的并发读操作，同时通过同步锁保证了，数据的完整性。
CHM允许多线程的读操作，同时根据默认并发级别（可以在构造函数中传入，默认16）个数，允许16个线程同时进入操作map，而SynchronizedMap和HashTable只允许一个线程进入操作map，但是如果是更新操作，比如remove，put，clear可以并发执行，所以不能保证最后返回的结果是最新的。如果只有很少的线程操作map，建议将并发级别设置少一些。
- 使用HashTable（基本是废弃的）
HashTable就是把HashMap套上了一个Synchronized
- 使用synchronizedMap()
使用synchronized 加上，但是这个是对某个Hash桶（数组的某个值）加锁，并不是整个map加锁，在锁定的时候别的线程也可以进行访问
10.LinkedHashMap
LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以用来实现LRU缓存策略。
HashMap，比如你放了一堆key-value对进去，后面的话呢如果你要遍历这个HashMap的话，遍历的顺序，并不是按照你插入的key-value的顺序来的。
LinkedHashMap，他会记录你插入key-value的顺序， 如果你在遍历的时候，他是按照插入key-value对的顺序给你遍历出来的
11.TreeMap
TreeMap使用红黑树存储元素，按key的自然顺序来排序。
2566
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
