- java集合
- java容器
- 数组的缺点
- 集合:
- 常见的集合
- Map接口
- HashMap的相关知识
- JDK1.7与JDK1.8HashMap的区别
- HashMap源码(JDK1.8)
- 存储结构
- 属性
- 构造方法
- put方法
- JDK1.7中HashMap在对线程环境中的问题
- HashTable和HashMap的区别
即集合、数组都是对多个数据进行存储 *** 作的结构数组的缺点
- 一旦初始化,其长度不可更改
- 对于增删等 *** 作不方便
- 数组一旦定义,其元素类型就确定了,不可更改
集合是存放数据对象引用的容器,集合可以避免数组的以上缺点常见的集合
Collection集合,Map集合
今天主要说HashMap,其余的大家可以自己了解
Map接口Map是一个键值对集合,存储键,值和之间的映射,Key无序,唯一;Value不要求有序,允许重复 Map常用的实现类:HashMap,TreeMap,HashTable,linkedHashMap,ConcurrentHashMapHashMap的相关知识 JDK1.7与JDK1.8HashMap的区别
- 底层由数组+链表改成数组+链表或红黑树
- 链表的插入方式由头插改成尾插
- 扩容时,JIK1.7需对原数组中的元素进行重新hash定位在原数组的位置,JDK1.8采用简单的逻辑判断,位置不变或旧容量大小
- 在插入时,JDK1.7先判断是否扩容再插入,JDK1.8先插入再判断是否扩容
- JDK1.7在new HashMap()时底层创建数组,JDK1.8在首次调用put方法时创建数组
存放所有结点的数组 transient Node属性[] table; //单向链表结点类 static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry,?> e = (Map.Entry,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } //计算哈希值 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //返回一个大于等于cap的数字,该数字要为2的次方数 static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
//数组初始化长度为16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //数组的最大长度为2^30 static final int MAXIMUM_CAPACITY = 1 << 30; //负载因子默认大小为0.75f static final float DEFAULT_LOAD_FACTOR = 0.75f; //树化阈值(链表长度超过8可能变为红黑树) static final int TREEIFY_THRESHOLD = 8; //树降级为链表的阈值 static final int UNTREEIFY_THRESHOLD = 6; //树化的另一个参数,当哈希表中的所有元素的个数超过64时,链表长度超过8的才会树化 static final int MIN_TREEIFY_CAPACITY = 64; //哈希表 transient Node构造方法[] table; //当前哈希表的元素个数 transient int size; //当前哈希表结构修改次数 transient int modCount; //扩容阈值,当哈希表中的元素超过阈值时,触发扩容 int threshold; //负载因子 //计算threshold,threshold = capacity(当前数组的大小) * loadFactor final float loadFactor;
//第一个:两个参数:初始化数组大小,负载因子 public HashMap(int initialCapacity, float loadFactor) { //initialCapacity必须大于0,且不能大于最大值2^30,如果大于则initialCapacity=2^30 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //loadFactor必须大于0 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //tableSizeFor()返回一个大于等于initialCapacity的数字,该数字要为2的次方数 this.threshold = tableSizeFor(initialCapacity); } //第二个:一个参数:初始化数组大小,调用第一个构造方法 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } //第三个:常用的构造方法 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } //第四个: public HashMap(Map extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }put方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab引用当前HashMap的散列表 //p是当前散列表的元素 //n是散列表数组的长度 //i是路由寻址((length-1)&hash) 结果 NodeJDK1.7中HashMap在对线程环境中的问题[] tab; Node p; int n, i; //第一次调用putVal时初始化hashMap对象中的散列表 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //如果通过路由算法得到的在数组中的该位置为null,则直接添加key-value(在此对p进行了赋值) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //e是临时的元素,不为null,找到了一个与要插入的key-value一致的key的元素 //k是元素的key Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //树化 else if (p instanceof TreeNode) e = ((TreeNode )p).putTreeval(this, tab, hash, key, value); else { //链表,而且当前链表的头元素与插入元素的key不一致 for (int binCount = 0; ; ++binCount) { //条件成立的话,迭代到最后一个元素也没有找到与插入元素key相同的元素,即将该元素插入到链表末尾 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //条件成立的话,说明当前链表的长度达到树化的标准,需要进行树化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //树化 *** 作 treeifyBin(tab, hash); break; } //条件成立的话,说明找到了相同key的元素,需要进行替换 *** 作 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //条件成立,说明找到了一个与插入元素key完全一致的数据进行替换 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //表示散列表结构被修改的次数,替换元素的value不计数 ++modCount; //插入新元素,size自增,若自增后大于扩容阈值,则触发扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
//HashMap扩容源码 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); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; //for循环中的代码,逐个遍历链表,重新计算索引位置,将老数组数据复制到新数组中 foreach (Entrye : table) { while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity);//假设线程一执行到这换成线程二 //将当前entry的next链指向新的索引位置,newTable[i]有可能为空,有可能也是个entry链,如果是entry链,直接在链表头部插入。 //第一次时 newTable[i] = null e.next = newTable[i]; newTable[i] = e; e = next; } } }
1)假设我们有两个线程
2)线程一被调度回来执行。
1,先是执行 newTalbe[i] = e;
2,然后是e = next,导致了e指向了key(7),
3,而下一次循环的next = e.next导致了next指向了key(3)
3)一切安好。
线程一接着工作。把key(7)摘下来,放到newTable[i]的第一个,然后把e和next往下移。
4)环形链接出现。
e.next = newTable[i] 导致 key(3).next 指向了 key(7)
注意:此时的key(7).next 已经指向了key(3), 环形链表就这样出现了。
- 底层数据结构不同:jdk1.7底层都是数组+链表,但jdk1.8 HashMap加入了红黑树
- Hashtable 是不允许键或值为 null 的,HashMap 的键值则都可以为 null。
- 初始化容量不同:HashMap 的初始容量为:16,Hashtable 初始容量为:11,两者的负载因子默认都是:0.75。
- 同步性不同: Hashtable是同步(synchronized)的,适用于多线程环境,
而hashmap不是同步的,适用于单线程环境。多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。 - Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)