HashMap 是以key-value来存储的数据结构。
底层的实现是:entry类型的数组。将key-value封装成entry对象。对于这种数据结构我们也称之为 散列链表。
HashMap 定义源码如下:
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
/**
* The default initial capacity - MUST be a power of two.
*/
//初始最大容量 必须是2的次幂
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
**/
//负载因子 表示散表的装满程度。
//如HashMap 的size>最大容量 * 0.75;表示HashMap实际容量已满,需要扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
//即是HashMap底层实现: 是以Entry 类型的数组;
transient Entry[] table;
/**
* The number of key-value mappings contained in this identity hash map.
*/
//存储的有效数据 key-value(会被封装成Entry对象) 个数
transient int size;
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
//该变量定义作为 该Map是否扩容的依据 ;即是实际容量。
//threshold = 最大容量*负载因子;
//如果size > threshold ;容器将会被扩容2倍,下面会讲到扩容。
int threshold;
HashMap 的构造方法:
//无参构造函数
public HashMap() {
//默认负载因子 0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
//实际容量 16*0.75
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
//Entry类型的数组
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
再来看看 内部定义Entry对象:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //hashMap key
V value; //hashMap value
final int hash; //通过对 key.hashCode()的值进行hash运算得出的值
Entry<K,V> next; //下一entry对象的引用。
先看下HashMap的数据结构图:
来看看HashMap put方法:
public V put(K key, V value) {
if (key == null)
//对key==null时处理
return putForNullKey(value);
// 对key的hashCode值进行hash运算
int hash = hash(key.hashCode());
// 得到的hash值与数组长度进行 & (位) 运算
// 得到的i即是数组中对应的下标位置
int i = indexFor(hash, table.length);
//对该entry数组下标为i的位置上entry对象的链表,进行遍历。
//如若存在该数据 则替换原先的value。
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;
}
//key==null的处理,定义一个常量NULL_KEY的Object对象,对它进行hash运算。
private V putForNullKey(V value) {
int hash = hash(NULL_KEY.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.key == NULL_KEY) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, (K) NULL_KEY, value, i);
return null;
}
//hash运算方法
static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}
//具体的hash算法
private static int oldHash(int h) {
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
//hash 与 数组长度 & (位)运算。得到数组对应下标的位置
static int indexFor(int h, int length) {
return h & (length-1);
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//提取原先数组下标下的entry对象
//如果该数组下标下没有entry,则e==null
Entry<K,V> e = table[bucketIndex];
//更改数组下标引用至新的entry对象
//并将新的entry对象的next指向数组下标原先的entry对象
//如若该数组下标不存在entry,则next引用为空。
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//鉴于查找效率的考虑,HashMap 的size > 实际容量时,则扩容。
if (size++ >= threshold)
//entry数组扩容2倍。
resize(2 * table.length);
}
//entry数组扩容2倍
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];
//数组扩容后,所有entry元素需要重新计算数组下标位置。
//生成新的散列链表
transfer(newTable);
table = newTable;
//重新计算实际容量
threshold = (int)(newCapacity * loadFactor);
}
//遍历hashMap下所有entry 通过 indexFor 方法重新计算数组位置。
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
HashMap get方法:
//get方法与put方法中处理是否存在该数据是类似的。
public V get(Object key) {
if (key == null)
// key==null的处理
return getForNullKey();
int hash = hash(key.hashCode());
//hash 、indexFor方法确定数组位置上entry的链表,进行遍历。
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.equals(k)))
return e.value;
}
return null;
}
- 大小: 62.3 KB
分享到:
相关推荐
用数据结构的思想实现java中的类hashmap
java中HashMap,LinkedHashMap,TreeMap,HashTable的区别
结合Java的HashMap中的一些优点,改进了C++ 的hash_map。 详细说明见我的博客:http://blog.csdn.net/mdj67887500/article/details/6907702
Map a = new HashMap(); //方法一 Iterator it = a.entrySet().iterator(); while (it.hasNext()) { Map.Entry pairs = (Map.Entry) it.next(); System.out.println(pairs.getValue()); } //以下方法需要jdk5以上...
《java编程思想》,Map结合HashMap获取键相关联的值
java Map实现的cache manager,定时清除缓存里面的值,使数据一致保持最新
比较Java原生的 3种Map的效率。 1. TreeMap 2. HashMap 3. ConcurrentSkipListMap 本测试查找方法使用Map的get方法,循环、离散获取。对于ConcurrentSkipListMap,获得顺序片段,可用subMap()方法,提取50w的子序列...
java hashmap 扩容因子为什么是0.75,官方给出的解释
HashMap和HashSet是Java Collection Framework的两个重要成员,其中HashMap是Map接口的常用实现类,HashSet是Set接口的常用实现类。虽然HashMap和HashSet实现的接口规范不同,但它们底层的Hash存储机制完全一样,...
JNI处理各种类型数据,不包含获取Java的HashMap;包含了java的工程和c++工程,可以查看代码,可以直接运行;同事包含了在网络上找的一些资料。
HashMap是Java中非常常用的一种数据结构,它实现了Map接口,用于存储键值对。HashMap内部使用哈希表来实现,通过将键映射到哈希表中的一个位置来快速查找和插入元素。 HashMap的主要特点是: 非线程安全:如果多个...
jsp上使用object[]看不懂吧?写vo太烦琐了?ok,都交给map吧、本工具类的使命就是让map代替所有的vo,让编程变得更美好。 附有详细的使用例子。 java精英团队十年编程精华。
java Map 遍历方法 Map map = new HashMap(); Iterator it = map.entrySet().iterator(); while (it.hasNext()) {
主要介绍了java在hashmap初始化时赋初值过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
实现类似于Java中的HashMap功能,作为一个脚本中的Collection使用,可自行扩展功能。
主要介绍了java中hashmap容量的初始化实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
Java中常用Map测试示例 包含 Map HashMap EnumMap等等
java map排序,hashmap,linkedmap,treemap,hashtable
通过引用【opevcsv】依赖,逐行读取数据 并转为Map,Object>格式,后续可以通过BeanUtil.MaptoBean()方法将map转为你需要的bean对象; csv文件必须带表头,bean对象命名符合驼峰格式; 通过此方法可以快速的将文件...
HashMap是一种常用的哈希表实现,用于存储键值对。它实现了Map接口,并且使用键的哈希值来快速定位和访问值。