1. ArrayList 和 Vector 的区别
ArrayList 和 Vector 底层实现原理都是一样得, 都是使用数组方式存储数据
Vector 是线程安全的, 但是性能比 ArrayList 要低.
ArrayList,Vector 主要区别为以下几点:
(1):Vector 是线程安全的, 源码中有很多的 synchronized 可以看出, 而 ArrayList 不是. 导致 Vector 效率无法和 ArrayList 相比;
(2):ArrayList 和 Vector 都采用线性连续存储空间, 当存储空间不足的时候, ArrayList 默认增加为原来的 50%,Vector 默认增加为原来的一倍;
(3):Vector 可以设置 capacityIncrement, 而 ArrayList 不可以, 从字面理解就是 capacity 容量, Increment 增加, 容量增长的参数.
2. 说说 ArrayList,Vector, LinkedList 的存储性能和特性
ArrayList 采用的数组形式来保存对象, 这种方法将对象放在连续的位置中, 所以最大的缺点就是插入和删除的时候比较麻烦, 查找比较快;
Vector 使用了 sychronized 方法 (线程安全), 所以在性能上比 ArrayList 要差些.
LinkedList 采用的链表将对象存放在独立的空间中, 而且在每个空间中还保存下一个链表的索引. 使用双向链表方式存储数据, 按序号索引数据需要前向或后向遍历数据, 所以索引数据慢, 是插入数据时只需要记录前后项即可, 所以插入的速度快.
3. 快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么?
1. 快速失败
原理是:
迭代器在遍历时直接访问集合中的内容, 并且在遍历过程中使用一个 modCount 变量. 集合在被遍历期间如果内容发生变化, 就会改变 modCount 的值. 每当迭代器使用 hasNext() 或 next() 遍历下一个元素之前, 都会先检查 modCount 变量是否为 expectmodCount 值. 如果是的话就返回遍历; 否则抛出异常, 终止遍历.
查看 ArrayList 源码, 在 next 方法执行的时候, 会执行 checkForComodification() 方法.
- @SuppressWarnings("unchecked")
- public E next() {
- checkForComodification();
- int i = cursor;
- if (i>= size)
- throw new NoSuchElementException();
- Object[] elementData = ArrayList.this.elementData;
- if (i>= elementData.length)
- throw new ConcurrentModificationException();
- cursor = i + 1;
- return (E) elementData[lastRet = i];
- }
- final void checkForComodification() {
- if (modCount != expectedModCount)
- throw new ConcurrentModificationException();
- }
这里异常的抛出条件是 modCount != expectedModCount 这个条件. 如果集合发生变化时修改 modCount 值刚好又设置为了 expectedModCount 值, 则异常不会抛出. 因此, 不能依赖于这个异常是否抛出而进行并发操作, 这个异常只建议用于检测并发修改的 bug.
2. 安全失败
采用安全失败机制的集合容器, 在遍历时不是直接在集合上访问的, 而是先复制原有集合内容, 在拷贝的集合上进行遍历.
原理:
由于迭代时是对原集合的拷贝进行遍历, 所以在遍历过程中对原集合所做的修改并不能被迭代器检测到, 所以不会触发 ConcurrentModificationException, 例如 CopyOnWriteArrayList.
缺点:
基于拷贝内容的优点是避免了 ConcurrentModificationException, 但同样地, 迭代器并不能访问到修改后的内容. 即: 迭代器遍历的是开始遍历那一刻拿到的集合拷贝, 在遍历期间原集合发生的修改迭代器是不知道的.
场景:
Java.util.concurrent 包下的容器都是安全失败的, 可以在多线程下并发使用, 并发修改.
快速失败和安全失败都是对迭代器而言的. 快速失败: 当在迭代一个集合时, 如果有另外一个线程在修改这个集合, 就会跑出 ConcurrentModificationException,java.util 下都是快速失败. 安全失败: 在迭代时候会在集合二层做一个拷贝, 所以在修改集合上层元素不会影响下层. 在 java.util.concurrent 包下都是安全失败.
4.HashMap 的数据结构
HashMap 的主干类是一个 Entry 数组 (jdk1.7) , 每个 Entry 都包含有一个键值队 (key-value).
我们可以看一下源码:
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;// 存储指向下一个 Entry 的引用, 单链表结构
- int hash;// 对 key 的 hashcode 值进行 hash 运算后得到的值, 存储在 Entry, 避免重复计算
- /**
- * Creates new entry.
- */
- Entry(int h, K k, V v, Entry<K,V> n) {
- value = v;
- next = n;
- key = k;
- hash = h;
- }
所以, HashMap 的整体结果如下
简单来说, HashMap 由数组 + 链表组成的, 数组是 HashMap 的主体, 链表则是主要为了解决哈希冲突而存在的, 如果定位到的数组位置不含链表 (当前 entry 的 next 指向 null), 那么对于查找, 添加等操作很快, 仅需一次寻址即可; 如果定位到的数组包含链表, 对于添加操作, 其时间复杂度为 O(n), 首先遍历链表, 存在即覆盖, 否则新增; 对于查找操作来讲, 仍需遍历链表, 然后通过 key 对象的 equals 方法逐一比对查找. 所以, 性能考虑, HashMap 中的链表出现越少, 性能才会越好.
5.HashMap 的工作原理
HashMap 基于 hashing 原理, 我们通过 put() 和 get() 方法存储和获取对象, 当我们将键值对传递给 put() 方法时, 它调用键对象的 hashCode() 方法来计算 hashcode, 让后找到 bucket 位置来存储值对象. 当获取对象时, 通过键对象的 equals() 方法找到正确的键值对, 然后返回对象.
我们看一下 put() 源码:
- public V put(K key, V value) {
- // 当 key 为 null, 调用 putForNullKey 方法, 保存 null 与 table 第一个位置中, 这是 HashMap 允许为 null 的原因
- if (key == null)
- return putForNullKey(value);
- // 计算 key 的 hash 值
- int hash = hash(key.hashCode()); // 计算 key hash 值在 table 数组中的位置
- int i = indexFor(hash, table.length); // 从 i 出开始迭代 e, 找到 key 保存的位置
- for (Entry<K, V> e = table[i]; e != null; e = e.next) {
- Object k;
- // 判断该条链上是否有 hash 值相同的 (key 相同)
- // 若存在相同, 则直接覆盖 value, 返回旧 value
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- V oldValue = e.value; // 旧值 = 新值
- e.value = value;
- e.recordAccess(this);
- return oldValue; // 返回旧值
- }
- }
- // 修改次数增加 1
- modCount++;
- // 将 key,value 添加至 i 位置处
- addEntry(hash, key, value, i);
- return null;
- }
通过源码我们可以清晰看到 HashMap 保存数据的过程为: 首先判断 key 是否为 null, 若为 null, 则直接调用 putForNullKey 方法. 若不为空则先计算 key 的 hash 值, 然后根据 hash 值搜索在 table 数组中的索引位置, 如果 table 数组在该位置处有元素, 则通过比较是否存在相同的 key, 若存在则覆盖原来 key 的 value, 否则将该元素保存在链头 (最先保存的元素放在链尾). 若 table 在该处没有元素, 则直接保存.
get() 源码:
- public V get(Object key) {
- // 若为 null, 调用 getForNullKey 方法返回相对应的 value
- if (key == null)
- return getForNullKey();
- // 根据该 key 的 hashCode 值计算它的 hash 码
- int hash = hash(key.hashCode());
- // 取出 table 数组中指定索引处的值
- for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
- Object k;
- // 若搜索的 key 与查找的 key 相同, 则返回相对应的 value
- if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
- return e.value;
- }
- return null;
- }
在这里能够根据 key 快速的取到 value 除了和 HashMap 的数据结构密不可分外, 还和 Entry 有莫大的关系, 在前面就提到过, HashMap 在存储过程中并没有将 key,value 分开来存储, 而是当做一个整体 key-value 来处理的, 这个整体就是 Entry 对象. 同时 value 也只相当于 key 的附属而已. 在存储的过程中, 系统根据 key 的 hashcode 来决定 Entry 在 table 数组中的存储位置, 在取的过程中同样根据 key 的 hashcode 取出相对应的 Entry 对象.
6.Hashmap 什么时候进行扩容呢?
这里我们再来复习 put 的流程: 当我们想一个 HashMap 中添加一对 key-value 时, 系统首先会计算 key 的 hash 值, 然后根据 hash 值确认在 table 中存储的位置. 若该位置没有元素, 则直接插入. 否则迭代该处元素链表并依此比较其 key 的 hash 值. 如果两个 hash 值相等且 key 值相等 (e.hash == hash && ((k = e.key) == key || key.equals(k))), 则用新的 Entry 的 value 覆盖原来节点的 value. 如果两个 hash 值相等但 key 值不等 , 则将该节点插入该链表的链头. 具体的实现过程见 addEntry 方法, 如下:
- void addEntry(int hash, K key, V value, int bucketIndex) {
- // 获取 bucketIndex 处的 Entry
- Entry<K, V> e = table[bucketIndex];
- // 将新创建的 Entry 放入 bucketIndex 索引处, 并让新的 Entry 指向原来的 Entry
- table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
- // 若 HashMap 中元素的个数超过极限了, 则容量扩大两倍
- if (size++>= threshold)
- resize(2 * table.length);
- }
这个方法中有两点需要注意:
一是链的产生. 这是一个非常优雅的设计. 系统总是将新的 Entry 对象添加到 bucketIndex 处. 如果 bucketIndex 处已经有了对象, 那么新添加的 Entry 对象将指向原有的 Entry 对象, 形成一条 Entry 链, 但是若 bucketIndex 处没有 Entry 对象, 也就是 e==null, 那么新添加的 Entry 对象指向 null, 也就不会产生 Entry 链了.
二, 扩容问题.
随着 HashMap 中元素的数量越来越多, 发生碰撞的概率就越来越大, 所产生的链表长度就会越来越长, 这样势必会影响 HashMap 的速度, 为了保证 HashMap 的效率, 系统必须要在某个临界点进行扩容处理. 该临界点在当 HashMap 中元素的数量等于 table 数组长度 * 加载因子. 但是扩容是一个非常耗时的过程, 因为它需要重新计算这些数据在新 table 数组中的位置并进行复制处理. 所以如果我们已经预知 HashMap 中元素的个数, 那么预设元素的个数能够有效的提高 HashMap 的性能.
7.HashSet 怎样保证元素不重复
都知道 HashSet 中不能存放重复的元素, 有时候可以用来做去重操作. 但是其内部是怎么保证元素不重复的呢?
打开 HashSet 源码, 发现其内部维护一个 HashMap:
- public class HashSet<E>
- extends AbstractSet<E>
- implements Set<E>, Cloneable, java.io.Serializable
- {
- static final long serialVersionUID = -5024744406713321676L;
- private transient HashMap<E,Object> map;
- private static final Object PRESENT = new Object();
- public HashSet() {
- map = new HashMap<>();
- }
- ...
- }
HashSet 的构造方法其实就是在内部实例化了一个 HashMap 对象, 其中还会看到一个 static final 的 PRESENT 变量;
想知道为什么 HashSet 不能存放重复对象, 那么第一步看看它的 add 方法进行的判重, 代码如下
- public boolean add(E e) {
- return map.put(e, PRESENT)==null;
- }
其实看 add() 方法, 这时候答案已经出来了: HashMap 的 key 是不能重复的, 而这里 HashSet 的元素又是作为了 map 的 key, 当然也不能重复了.
顺便看一下 HashMap 里面又是怎么保证 key 不重复的, 代码如下:
- public V put(K key, V value) {
- if (table == EMPTY_TABLE) {
- inflateTable(threshold);
- }
- if (key == null)
- return putForNullKey(value);
- int hash = hash(key);
- int i = indexFor(hash, table.length);
- 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++;
- addEntry(hash, key, value, i);
- return null;
- }
其中最关键的一句:
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
调用了对象的 hashCode 和 equals 方法进行判断, 所以又得到一个结论: 若要将对象存放到 HashSet 中并保证对象不重复, 应根据实际情况将对象的 hashCode 方法和 equals 方法进行重写
来源: https://www.cnblogs.com/SuperManer/p/11867374.html