HashMap
- 无序（每次resize的时候都会变）
- 非线程安全
- key和value都看可以为null
- 使用数组和链表实现
- 查找元素的时候速度快
几个重要属性：
- loadFactor：用来计算threshold
- threshold：决定map是否需要扩容，threshold = capacity * loadFactor
构造函数
// 构造函数中初始化了threadhold和loadFactor
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;threshold = initialCapacity;init();
}put
public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)// 添加key为null的元素，因为key不能重复，只能有一个key为null的元素return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);// 先查找链表里面是否存在key相同的entry，如果有就直接替换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;}}// 如果没有key相同的entry，新加一个entrymodCount++;addEntry(hash, key, value, i);return null;
}// 取key的哈希值
final int hash(Object k) {int h = hashSeed;if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h ^= k.hashCode();// number of collisions (approximately 8 at default load factor).// 因为hashCode如果写的不好的话可能会使碰撞出现的次数较多，所以使用移位运算再次hash// 使用这中方法hash的原因：http://www.iteye.com/topic/709945h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {// 如果size大于阈值threshold则扩容resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}// 将entry添加到链表中createEntry(hash, key, value, bucketIndex);
}void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}Entry[] newTable = new Entry[newCapacity];// 每次扩容之后都要重新散列元素，因为table.length 变化了transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}// 新建一个entry，并放入链表的头部
void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}
Hashtable
- key和value都不能为null
- 线程安全（但是效率没有ConcurrentHashMap高，读写锁，分段锁）
- key必须实现hashCode和equals方法
- 无序
在实现上除了put、get等方法是synchronized和hash方法不同之外,基本和HashMap一样
