1:参考
http://www.ibm.com/developerworks/cn/java/j-lo-hash/
3:java map对比性能
http://blog.hongtium.com/java-map-skiplist/
测试例子:
public class MapTest { @Test public void hashMapTest() { Map<String, Object> map=new HashMap<String, Object>(); map.put(null, null); map.put("a", null); map.put(null, "a"); map.put("b", "b"); map.put("b", "abccccccccccc"); System.out.println(map.get(null)); System.out.println(map.get("a")); System.out.println(map.get("b")); } }
2: HashMap的结构关系:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
3:Map<K,V> 接口定义了一些map的方法
public interface Map<K,V> { boolean isEmpty(); boolean containsKey(Object key); V put(K key, V value); V remove(Object key); void putAll(Map<? extends K, ? extends V> m); void clear(); Set<K> keySet(); Collection<V> values(); Set<Map.Entry<K, V>> entrySet(); //保存map数据类型的接口 interface Entry<K,V> { K getKey(); V getValue(); V setValue(V value); boolean equals(Object o); int hashCode(); } boolean equals(Object o); int hashCode(); }
4:AbstractMap<K,V>是TreeMap和hashMap等具体实现的父类 抽象, 具体的put 和get操作子类具体实现
5:map.put(null, null)或者map.put(null, "aaa") 对null key的处理
源码:
public V put(K key, V value) { if (key == null) return putForNullKey(value); // 处理key值为null的情况 int hash = hash(key.hashCode()); // 根据类型的hashcode值算hash,使得h //使得hash的发布更加均匀 减少重复 int i = indexFor(hash, table.length); //获取对象的保存位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { //已经有key了 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; }
HashMap可以处理key为null的情况,在putForNullKey(value)中
private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { // 在下表0处理保存null的值,如果e不为空,处理冲突 if (e.key == null) { // 是否已经存在 替换新的value V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); // 在下表0处添加key为null的value return null; }
HashMap的key为null,的put过程就到此结束.
下面看下key不为null的情况,更具key.hashCode的方法使用hash()函数计算,hash值,看下hash()
static int hash(int h) { // 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); }
这个hash()的目的,是因为key.hashCode()的计算出来的重复可能性比较高,所以hash一次减少重复,具体为什么要这样写,也不太明白?据说是《计算机程序设计艺术》里有这个解释,增加了hash的随机分布性。
int i = indexFor(hash, table.length); //获取对象的在数组中保存位置
hash()后的值,可能比table.length大很多; 怎么保证hash()后的在数组的范围之内;hash() % table.length 也是可以,但是 效率肯定是没有& 位移的操作快,
/** * 返回对象的保存位置 * lengt为2的倍数 * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }
所有在动态扩展数组大小的时候都是2的倍速
如果是key是的value是空 就会走
addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); //重新申请空间 }
Entry<K, V>结构:
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; // 链表的形式HASH处理冲突 final int hash; /** * Creates new entry. * 创建一个-- */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } }
数组空间满了, 必须要重新分配空间:resize(2 * table.length); //重新申请空间
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); // 老数据复制到新的里面 table = newTable; threshold = (int)(newCapacity * loadFactor); // 容量大小 }
上面没有说到的是 new HashMap()
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } static final float DEFAULT_LOAD_FACTOR = 0.75f; //hash的装载因子
复制老数据到新的
/** * Transfers all entries from current table to newTable. */ 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取数据,可以自己看下;如果hashCode很不好,会导致hashmap在列表中取数据让其退化成链表,则是O(N).即便是O(1),也要注意,实际上计算hash用了好几步,绝对比直接从数组中获取某个元素的O(1)时间要长的多。
hashmap的优化:
1: 由于hashmap的容量,受限于loadfactor*capacity=thredload,然后进行扩容,重新hash
所以对可以预知的容量,最好new HashMap(18), 避免扩容操作
2: 当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。
掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,程序员无需改变负载因子的值。
如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中 Entry 的数量一直不会超过极限容量(capacity * load factor),HashMap 就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能。当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的 Entry 数组),因此创建 HashMap 时初始化容量设置也需要小心对待。
上面说法是相对的,负载因子大,hash冲突可能会增加,查询效率可能下降; 小的 扩容比较频繁
怎么很好的讲解原理:
面试的时候:
1:
相关推荐
HashMap源码深度剖析,面试必备
HashMap源码(JDK1.7,含注释)
hashmap源码,可以看看http://blog.csdn.net/wabiaozia/article/details/50684556
HashMap的部分源码解析
HashMap源码流程图 一图解析HashMap源码流程 // 默认的HashMap中数组的长度 16 static final int DEFAULT_INITIAL_CAPACITY = 1 ; // aka 16 // HashMap中的数组的最大容量 static final int MAXIMUM_CAPACITY = 1 ...
精确的版本号是jdk-7u80。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
《HashMap源码剖析》 HashMap是Java编程语言中一个非常重要的数据结构,它属于集合框架的一部分,提供了键值对(Key-Value)的存储方式。HashMap在内部使用了一个数组和链表来实现,实现了快速的查找、插入和删除...
精确的版本号是jdk-8u181。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
《手写HashMap源码解析——深入理解数据结构与算法》 HashMap是Java编程语言中一个常用的集合类,它提供了一种高效、灵活的键值对存储方式。在面试过程中,尤其是2020年及以后的技术面试中,深入理解HashMap的实现...
在Java编程语言中,HashMap是集合框架中一个重要的类,用于存储键值对的数据结构。面试中,HashMap的源码分析与实现是一个常见的考察点,...深入学习和实践HashMap源码,能够帮助我们更好地理解和优化Java应用程序。
HashMap 源码实现红黑树添加元素和删除元素 HashMap 中使用红黑树来存储元素,是为了提高查找、插入和删除操作的性能。红黑树是一种自平衡二叉树,可以保持二叉树的平衡,从而获得较高的查找性能。 红黑树的创建...
HashMap 是 Java 中最常用的集合类之一,它是基于哈希表实现的,提供了高效的数据存取功能。HashMap 的核心原理是将键(key)通过哈希函数转化为数组索引,然后将键值对(key-value pair)存储在数组的对应位置。...
hashmap源码 Table Of Contents day01_JAVA语言概述与基本语法:标识符、变量也变量分类、源码_反码_补码、进制转换、编码与字符集 day02_基本语法.运算符:算术运算符、赋值运算符、比较运算符、逻辑运算符、位...
1.面试必考之HashMap源码分析与实现 伸缩性角度看HashMap的不足
HashMap源码,,,,,,写个笔记方便后续学习
《HashMap 源码解析——JDK11版本》 HashMap是Java中广泛使用的非同步散列表,其设计和实现是高效且灵活的。在JDK1.8之前,HashMap的底层数据结构采用的是数组+链表的方式,这种方式称为“拉链法”来解决哈希冲突。...