add方法会把元素加到表尾而不是表头；LinkedList可以当做栈和队列使用是因为实现了Deque接口，有队列poll、offer方法和栈push、pop方法，数据结构是基于链表来实现的；

小结

相比ArrayList而言，LinkedList数据的增加，删除，不会有增容和数组拷贝，效率更高效。对于查询和修改，LinkedList需要根据指针依次检查，ArrayList是随存随取，ArrayList会更高效。有一点需要注意，很多时候都会谈到性能问题，但是对于数据量小的情况影响真的不大，哪一种数据结构方便就使用哪种就好了，不用去纠结和比较。

HashMap

+ HashMap 是一个采用哈希表（数组+链表）实现的键值对集合，继承自 AbstractMap，实现了 Map 接口 。

+ 两个关键因子：初始容量、加载因子

+ 插入、获取的时间复杂度基本是 O(1)

数据结构：


源码

构造函数：

static final int DEFAULT_INITIAL_CAPACITY = 4;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY) {

initialCapacity = MAXIMUM_CAPACITY;

} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {

initialCapacity = DEFAULT_INITIAL_CAPACITY;

}

if (loadFactor <= 0 || Float.isNaN(loadFactor))

throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

threshold = initialCapacity;

init();

}

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

public HashMap() {

this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);

}

public HashMap(Map<? extends K, ? extends V> m) {

this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,

DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);

inflateTable(threshold);

putAllForCreate(m);

}

HashMap的构造函数有四个，而最终都会执行`HashMap(int initialCapacity, float loadFactor)`构造函数，直播，无论是默认构造、初始容量构造，还是初始集合构造。主要有2点：

+ DEFAULT_INITIAL_CAPACITY默认初始容量，DEFAULT_LOAD_FACTOR装载因子，这是个经验值。

+ 可以指定初始容量，以及装载因子。一般情况都会使用默认的装载因子。

下面来Look下put（新增和修改）、remove、get源码：

public V put(K key, V value) {

if (table == EMPTY_TABLE) {

inflateTable(threshold);

}

if (key == null)

return putForNullKey(value);

int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);

int i = indexFor(hash, table.length);

for (HashMapEntry<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;

}

static int indexFor(int h, int length) {

return h & (length-1);

}

void addEntry(int hash, K key, V value, int bucketIndex) {

if ((size >= threshold) && (null != table[bucketIndex])) {

resize(2 * table.length);

hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;

bucketIndex = indexFor(hash, table.length);

}

createEntry(hash, key, value, bucketIndex);

}

void createEntry(int hash, K key, V value, int bucketIndex) {

HashMapEntry<K,V> e = table[bucketIndex];

table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);

size++;

}

public V remove(Object key) {

Entry<K,V> e = removeEntryForKey(key);

return (e == null ? null : e.getValue());

}

public V get(Object key) {

if (key == null)

return getForNullKey();

Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();

}

+ put函数

if (key == null)

return putForNullKey(value);

由此可知key可以为空。

int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);

int i = indexFor(hash, table.length);