红色代表接口，蓝色代表抽象类，绿色代表并发包中的类，灰色代表早期进程安全的类（基本上已过期）
ArrayList
基于数组，支持快速随机访问
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable // 实现了RandomAccess表示支持快速随机访问
数组默认大小为10，基于数组实现
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData; // non-private to simplify nested class access
添加元素时会调用add（）方法，同时使用ensureCapacityInternal（）方法来保证调用add（）方法时数组的容量，当数组容量不够时，会调用grow（）方法进行扩容。
扩容代码：
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容大小为原来的1.5倍 ......
......
// minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); // 将原来的数组拷贝进新的数组，扩容的代价高 }
删除元素是会调用system.arraycopy()方法，将index+1后面的元素都复制到index的位置上，代价高
System.arraycopy(elementData, index+1, elementData, index, numMoved);
LinkedList
基于双向链表，在任意位置添加删除元素比ArrayList快。
数据类型：
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
HashMap
基于JDK1.7源码
Entry内部类存储KV键值对
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } }
存储所有节点的数组：
transient Entry[] table;
- HashMap使用拉链法将键值将KV数据打散分布在不同table[i]中。
- HashMap 通过 key 的 hashCode 经过hash()处理过后得到 hash 值，然后通过 hash & (length - 1)判断当前元素存放的位置（length为table[]的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就插入在链表头部。
HashMap添加元素，执行put（）操作，会先执行hash（）方法计算hash值，然后计算哈希桶的位置，hash值重复则覆盖，不重复则头插法插入链表，最后调用addEntry（）方法添加键值对，如果键为null，默认插入table[0]上。
计算hash代码
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
计算哈希桶的位置
int hash = hash(key); int i = indexFor(hash, table.length);
static int indexFor(int h, int length) { return h & (length-1); }
HashMap扩容：
扩容使用resize（）方法，扩容大小为原来table[]数组的的两倍，然后调用transfer（）方法，将 oldTable 的所有键值对重新插入 newTable 中，扩容时会重新计算哈希桶的位置。
resize(2 * table.length);
ConcurrentHashMap
并发下使用的线程安全的 HashMap 的替代品。
数据存储结构
static final class HashEntry<K,V> { final int hash; final K key; volatile V value; volatile HashEntry<K,V> next; }
final Segment<K,V>[] segments;
Segment核心类继承自重入锁ReentrantLock
static final class Segment<K,V> extends ReentrantLock implements Serializable {
static final int DEFAULT_CONCURRENCY_LEVEL = 16; // 默认并发级别为16
ConcurrentHashMap 采用了分段锁（Segment）技术，每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶。
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
