文章目录
- Java中的集合类有哪些？如何分类的？
- 为什么索引数组从0开始？从1开始可以吗？
- 如何实现数组和ArrayList之间的转换？
- ArrayList和LinkedList的区别是什么？
- 如何构建线程安全的List？
- HashMap的实现原理
- HashMap的get方法的具体流程？
- HashMap的put方法的具体流程？
- HashMap的扩容机制是什么？
- 为什么HashMap的数组长度一定是2的次幂
- hashMap的寻址算法
- HashMap、Hashtable和ConcurrentHashMap的区别？
- HashMap在多线程下会出现什么问题？
- Set如何保证元素不可重复的？
- Set.contains()的时间复杂度？
Java中的集合类有哪些？如何分类的？
- Java中的集合类主要由两大接口派生而来：一个是
Collection接口，主要用于存放单一元素；另一个是Map接口，主要用于存放键值对。 - Collection接口下又有三个主要的子接口:
List、Set、Queue List接口下的实现类：ArrayList、LinkedList、VectorSet接口下的实现类：HashSet、TreeSetQueue接口下的实现类：PriorityQueue、ArrayDeque、LinkedListMap结构下的实现类：HashMap、TreeMap、Hashtable
为什么索引数组从0开始？从1开始可以吗？
- 根据数组索引获取元素的时候，会用索引和寻址公式来计算所对应的数据，寻址公式为数组的首地址+索引*存储数据的类型大小
- 索引如果从1开始的话，寻址公式中，就增加了一次减法操作，对于CPU来说增加了一条指令，性能不高
如何实现数组和ArrayList之间的转换？
- 数组转
ArrayList：使用JDK中Java.util.Arrays工具的asList方法 ArrayList转数组：使用List的toArray方法。无参toArray返回Object数组，传入初始化长度的数组对象，返回该对象数组
Arrays.asList转换list之后，如果修改了数组的内容，list会受影响，因为它的底层使用的Arrays
类中的一个内部类ArrayList来构造的集合，在这个集合的构造器中，把我们传入的这个集合进行了
包装而已，最终指向的都是同一个内存地址
list用了toArray转数组后，如果修改了list内容，数组不会影响，当调用了toArray以后，在底层
是它是进行了数组的拷贝，跟原来的元素就没啥关系了，所以即使list修改了以后，数组也不受影
响
ArrayList和LinkedList的区别是什么？
- 底层数据结构：ArrayList是动态数组数据结构实现，LinkedList是双向链表的数据结构实现的
- 操作效率：
- 查找：ArrayList按照下标查询的时间复杂度O(1)，LinkedList不支持下标查询；如果查找未知索引， ArrayList需要遍历，链表也需要遍历链表，时间复杂度都是O(n)
- 插入和删除：ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)；LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)。（这里链表插入和删除为O(n)的原因是需要先遍历链表找到具体位置，然后再执行操作，若单纯说在指定位置插入删除则为O(1)）
- 线程安全：ArrayList和LinkedList都不是线程安全的，
- 占用内存大小：ArrayList底层是数组，内存连续，节省内存，LinkedList 是双向链表需要存储数
据，和两个指针，更占用内存
如何构建线程安全的List？
- Vector：它和ArrayList在常用方法的实现上很相似，不同的只是它采用了同步关键词synchronized修饰方法。
public void add(int index, E element) {
insertElementAt(element, index);
}
...
// 使用了synchronized关键词修饰
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
- Collections.synchronizedList：同样是使用了同步代码块,无论是读操作还是写操作，它都会进行加锁，当线程的并发级别非常高时就会浪费掉大量的资源,因此有了下面的第三种线程安全的List的实现。
final Object mutex;
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
- CopyOnWriteArrayList：写操作的时候复制数组，在该类的使用过程中，读读操作和读写操作都不互斥。读操作和写操作位于不同的数组上，因此它们不会发生安全问题。
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();
}
}
HashMap的实现原理
- 数据结构：数组链表或者红黑树
- put元素时：
- 根据key的hashcode计算对象元素在数组中的下标
- key相同，覆盖原始值；key不相同，则将当前的key-value放入链表或者红黑树中
- get元素时：根据Hash值找到对应的下标，再进一步判断key是否相同，从而找到对应值
HashMap的get方法的具体流程？
- 计算key的Hash值，并通过Hash值计算出在数组中的索引位置
- 如果该位置为null，说明没有找到对应的键值对，返回null
- 如果该位置不为null，遍历该位置上的元素，如果找到了与当前key相等的键值对，则返回，否则返回null
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) {
// 定位到桶的位置元素就是想要获取的key对应的，则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 定位到的位置不是想要的
if ((e = first.next) != null) {
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;
}
HashMap的put方法的具体流程？
- 判断断键值对数组table是否为空或者为null，否则执行resize()进行扩容(初始化)
- 根据键值key计算hash值得到数组索引
- 判断table[i]==null，条件成立，直接新建节点添加
- 如果table[i]==null ,不成立
- 如果key存在，则直接覆盖
- 不存在的话， 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
- 遍历table[i]，链表的尾部插入数据，然后判断链表是否需要转换成红黑树，如果转换成红黑树，在红黑树中执行插入操作
- 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），
如果超过，进行扩容
HashMap的扩容机制是什么？
- 在添加元素或初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次每次扩容都是达到了扩容阈值（数组长度 *0.75）
- 每次扩容的时候，都是扩容之前容量的2倍
- 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
- 没有hash冲突的节点，则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置
- 如果是红黑树，走红黑树的添加
- 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash &oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上（拆分链表）
为什么HashMap的数组长度一定是2的次幂
- 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模(a % b = a & (b - 1))
- 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置
hashMap的寻址算法
- 首先获取key的hashCode值，然后右移16位 异或运算原来的hashCode值，主要作用就是使原来的hash值更加均匀，减少hash冲突
- 通过与运算实现hash值对数组大小取模得到下标
HashMap、Hashtable和ConcurrentHashMap的区别？
- 线程安全：
- HashMap是非线程安全的
- Hashtable中的方法是同步的，所以他是线程安全的
- ConcurrentHashMap在JDK 1.8之前使用分段锁保证线程安全，ConcurrentHashMap默认情况下将hash表分为16个桶(分片)，在加锁的时候，针对每个单独的分片进行加锁，其他分片不受影响。锁的粒度更细，所以他的性能更好。ConcurrentHashMap在JDK 1.8中，采用了一种新的方式来实现线程安全，即使用了CAS+synchronized，这个实现被称为“分段锁”的变种，也被称为“锁分离"，它将锁定粒度更细，把锁的粒度从整个Map降低到了单个桶。
- 继承关系：
- HashMap继承的抽象类AbstractMap实现了Map接口
- ConcurrentHashMap同样继承了抽象类AbstractMap，并且实现了ConcurrentMap接口
- Hashtable是基于陈旧的Dictionary类继承来的
- 扩容机制：
- HashMap和ConcurrentHashMap的默认初始容量为16，默认的加载因子为0.75，即当HashMap中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍，并将原来的元素重新分配到新的桶中。
- Hashtable，默认初始容量为11，默认的加载因子为0.75，即当Hashtable中元素个数超过容量的75%时，会进行扩容操作。扩容时，容量会扩大为原来的两倍加1，并将原来的元素重新分配到新的桶中。
- 允不允许null值：
- HashMap中，null可以作为键或者值都可以。
- ConcurrentHashMap和Hashtable中，key和value都不允许为nul
HashMap在多线程下会出现什么问题？
- 元素丢失：当多个线程同时执行 put 操作时，如果它们计算出的索引位置相同，就会造成前一个 key被后一个 key 覆盖的情况，从而导致元素的丢失
- get为null：当一个线程执行 put 操作导致扩容时，而另一个线程同时执行 get 操作，有可能会导致 get 返回 null 的情况。是因为在扩容过程中，HashMap 的结构发生了变化，get 操作可能会在旧的结构中查找元素而导致找不到
- 扩容死循环：在 JDK1.7 中，HashMap 使用头插法插入元素，当多个线程同时进行扩容操作时，可能会导致环形链表的形成从而陷入死循环。为了解决这个问题，在」DK1.8 中采用了尾插法插入元素，保持了链表元素的顺序，避免了死循环的问题
Set如何保证元素不可重复的？
- 在HashSet中，基本的操作都是有HashMap底层实现的，因为HashSet底层是用HashMap存储数据的。当向HashSet中添加元素的时候，首先计算元素的hashCode值然后通过扰动计算和按位与的方式计算出这个元素的存储位置，如果这个位置为空，就将元素添加进去;如果不为空，则用equals方法比较元素是否相等，相等就不添加，否则找个空位添加。
- TreeSet的底层是TreeMap，元素在插入TreeSet时compareTo()方法要被调用，所以TreeSet中的元素要实现Comparable接口。TreeSet作为一种Set，它不允许出现重复元素。TreeSet是用compareTo()来判断重复元素的。
Set.contains()的时间复杂度？
- HashSet底层是HashMap实现的，HashMap的containskey()方法的底层实现原理是依据hash()和equals()方法，首先根据key计算出对应的哈希值(O(1))并与hash表中的值比较，不同就继续比较，相同则再比较元素是否相同，二者都相同则得到的是true，否则说明Map中没有这个key，所以，HashSet的contains()方法的时间复杂度为O(1)~O(n)，主要是看相同的hash值的元素有多少个
- TreeSet 基于红黑树实现，因此 contains 方法的时间复杂度是 O(log n)