数据结构---Java---HashMap---JDK1.7
2024-10-07 17:36:50
源码解读
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{ //*******内部类
//Enrty<K,V> 单向链表
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash; /**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
} //*******属性
static final Entry<?,?>[] EMPTY_TABLE = {};
//Entry<K,V>[]数组实现
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
final float loadFactor;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //*******构造器
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
} 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();
} public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} //********方法
//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);
} //put方法
public V put(K key, V value) { //在put操作时,判断数组是否为空,再数组初始化容量
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key); //定位数组索引i
int i = indexFor(hash, table.length); //如果table[i]存在,然后使用单向链表解决冲突
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k; //如2个key 的hash值相等,并且 equals也相等,则覆盖旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
} modCount++; //如果table[i]没有,添加元素
addEntry(hash, key, value, i);
return null;
} //数组容量初始化
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//根据计算容量初始化数组
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
} //定位数组索引i
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
} void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) { //扩容为原来的2倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
} 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];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
} //旧数组数据迁移至新数组(此处会引起 环形链表 )
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length; //遍历旧数组中的每一项
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
} 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++;
} public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue();
} final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
} int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
}
最新文章
- web前端基础知识-(八)Django进阶之数据库对象关系映射
- PHP服务缓存优化之ZendOpcache、xcache、eAccelerator
- 【2016-10-27】【坚持学习】【Day14】【GlobalAssemblyInfo 】
- Windows下安装Ruby
- HTML5 Viewport Meta Tag
- flexbox 伸缩布局盒
- phpstorm界面不停的indexing,不停的闪烁
- [POI2006]OKR-Periods of Words(KMP)
- 06. Matplotlib 2 |折线图| 柱状图| 堆叠图| 面积图| 填图| 饼图| 直方图| 散点图| 极坐标| 图箱型图
- HDU 4283 You Are the One ——区间dp
- 笔记本 原来win10系统改装win7系统遇到 invaid signature detected.check secure boot policy setup问题
- asp.net 发送电子邮件本地测试正常,但服务器上异常的解决办法
- MATLAB 的循环语句
- 几个解决k染色问题的指数级做法
- 【转】Java 异步处理简单实践
- P1796 汤姆斯的天堂梦
- tiny6410的linux操作系统实验开发
- UGUI 事件穿透规则
- *2_3_5_加入reference model
- ARC 101 C - Candles
热门文章
- 理解";__repr__";
- 【leetcode】1021. Remove Outermost Parentheses
- leetcode-167周赛-1293-网格中的最短路径
- 一款易用、高可定制的vue翻页组件
- Delphi fmx 找不到android设备解决办法
- 【bzoj1185】[HNOI2007]最小矩形覆盖 (旋转卡壳)
- git merge 上线操作流程
- Codeforces 510C (拓扑排序)
- 左手Mongodb右手Redis redis操作
- 10. Jmeter-后置处理器一