怎样做娱乐网站,网站排名,平安网站建设公司,有域名可以自己做网站吗简介
HashMap 是一种基于哈希表的 Map 接口实现#xff0c;它存储键值对#xff08;key-value pairs#xff09;#xff0c;并允许使用键来快速检索值。在 Java 中#xff0c;HashMap 是 java.util 包的一部分#xff0c;它不是同步的#xff0c;这意味着它不是线程安全…简介
HashMap 是一种基于哈希表的 Map 接口实现它存储键值对key-value pairs并允许使用键来快速检索值。在 Java 中HashMap 是 java.util 包的一部分它不是同步的这意味着它不是线程安全的。如果你需要线程安全的版本可以使用 ConcurrentHashMap。
以下是 HashMap 的一些关键特性
允许空键和空值HashMap 允许键和值为 null。非同步HashMap 不是线程安全的。如果你需要线程安全的 HashMap可以使用 Collections.synchronizedMap 方法包装一个 HashMap或者使用 ConcurrentHashMap。迭代顺序从 JDK 1.8 开始HashMap 保证在并发访问的情况下迭代顺序是可预测的即按照插入顺序进行迭代。初始容量和加载因子HashMap 可以指定初始容量和加载因子来优化性能。初始容量是哈希表中桶的数量加载因子是一个影响哈希表扩展的阈值。哈希冲突当两个键的哈希码相同或者哈希码经过数组索引计算后位置相同时会发生哈希冲突。HashMap 使用链表在 JDK 1.8 之后是链表和红黑树的结合来解决冲突。
以下是 Java 中 HashMap 的一个简单示例
import java.util.HashMap;public class HashMapExample {public static void main(String[] args) {HashMapString, Integer map new HashMap();map.put(apple, 1);map.put(banana, 2);map.put(cherry, 3);// 获取值Integer cherryValue map.get(cherry);System.out.println(Cherry value: cherryValue);// 检查键是否存在if (map.containsKey(banana)) {System.out.println(Banana is in the map.);}// 删除键值对map.remove(apple);// 遍历 HashMapfor (Map.EntryString, Integer entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());}}
}在这个示例中我们创建了一个 HashMap 实例并添加了一些键值对。然后我们获取了一个值检查了一个键是否存在删除了一个键值对并遍历了 HashMap。
源码
hashmap成员变量
//创建 HashMap 时未指定初始容量情况下的默认容量也就是16 static final int DEFAULT_INITIAL_CAPACITY 1 4; //HashMap 的最大容量也就是2的30次方1 073 741 824static final int MAXIMUM_CAPACITY 1 30;//HashMap 默认的装载因子,当 HashMap 中元素数量超过 容量*装载因子 时进行resize()操作也就是扩容static final float DEFAULT_LOAD_FACTOR 0.75f;//用来确定何时将解决 hash 冲突的链表转变为红黑树static final int TREEIFY_THRESHOLD 8;// 用来确定何时将解决 hash 冲突的红黑树转变为链表static final int UNTREEIFY_THRESHOLD 6;//当需要将解决 hash 冲突的链表转变为红黑树时需要判断下此时数组容量若是由于数组容量太小(小于MIN_TREEIFY_CAPACITY)导致的hash冲突太多则不进行链表转变为红黑树操作会先利用resize()函数对hashMap扩容static final int MIN_TREEIFY_CAPACITY 64;// 这个就是hashMap的内部数组了而Node则是链表节点对象。
transient NodeK,V[] table;// 数组扩容阈值。
int threshold;hashmap的节点的数据结构 static class NodeK,V implements Map.EntryK,V {//存储了键对象的哈希码用于快速定位桶的位置final int hash;//存储键对象final K key;//存储与键相关联的值V value;//指向下一个节点的引用用于解决哈希冲突当链表长度好过一定阈值列表会转成红黑树以提高搜索效率NodeK,V next;Node(int hash, K key, V value, NodeK,V 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;}}hashmap的put方法 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** Implements Map.put and related methods.** param hash hash for key* param key the key* param value the value to put* param onlyIfAbsent if true, dont change existing value 当存入键值对时如果该key已存在是否覆盖它的value。false为覆盖true为不覆盖* param evict if false, the table is in creation mode. 用于子类* return previous value, or null if none*///final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab;//内部数组NodeK,V p; //hash对应的索引中的首节点int n, i;//n 内部数组的长度 i hash对应的索引位//首次put时内部数组为空扩充数组if ((tab table) null || (n tab.length) 0)n (tab resize()).length;//计算数组索引计算该索引位置的首节点如果为null添加一个新节点if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;//如果首节点的key和要存入的key相同那么直接覆盖value值if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//如果首节点是红黑树将键值对插入到红黑树中else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {//到达链表尾部if ((e p.next) null) {//向链表尾部插入新节点p.next newNode(hash, key, value, null);//判断链表元素8-1 尝试转换红黑树 : 不转换if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//转换之前会先判断当前数组容量是否64 转换红黑树 resize扩容treeifyBin(tab, hash);break;}//检查链表中是否已包含keyif (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//如果key存在则覆盖valueif (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}//fail-fast机制 // Java集合中的一种错误检测机制当多个线程对集合进行结构性的改变时有可能会出发fail-fast机制这个时候会抛出ConcurrentModificationException异常。modCount;//集合实际被修改的次数//如果集合容量大于阈值则进行扩容if (size threshold)resize();afterNodeInsertion(evict);return null;}hashmap的resize扩容操作 final NodeK,V[] resize() {//旧的数组 hashmap的内部数组NodeK,V[] oldTab table;//旧的数组长度 如果数组长度为空0不为空则是数组的长度int oldCap (oldTab null) ? 0 : oldTab.length;//旧的扩容阈值int oldThr threshold;int newCap, newThr 0;//旧的数组长度大于0if (oldCap 0) {//旧的数组长度是否大于等于hashmap的最大容量if (oldCap MAXIMUM_CAPACITY) {//扩容阈值就是 int的最大值2的31次方-1threshold Integer.MAX_VALUE;//此时已经是最大值了不扩容直接返回旧数组return oldTab;}//新数组长度2*旧数组长度 小于hashmap的最大容量 且旧数组长度大于默认值16 13644391557else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}//旧数组长度等于0 且旧的阈值大于0 新的初始数组容量被置为旧的阈值else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr;//创建一个新的链表SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;//处理旧链表尾节点if (e.next null)newTab[e.hash (newCap - 1)] e;//如果是红黑树else if (e instanceof TreeNode)//将一个红黑树节点分裂成两个子树。这个过程通常发生在并发环境下当哈希表的大小超过某个阈值时会将链表转换为红黑树以提高搜索效率。// 这里的 split 方法就是将一个红黑树节点分裂成两个子树并将它们重新链接到哈希表的桶中。((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;//根据节点的哈希值与旧容量 oldCap 的按位与操作的结果将它们分配到两个新的链表中。e.hash oldCap 的结果决定了节点应该属于哪个新链表。do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;}hashmap的get方法 public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;}get方法查找对应节点 final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;//判断容器是否为空if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {//查看哈希值是否与首节点的哈希值相同if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;//首节点不是目标节点且首节点的下一个节点不为空if ((e first.next) ! null) {//红黑树结构查找节点if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);do {//链表结构查找节点if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;}HashMap中的死锁
HashMap会造成死锁因为HashMap是线程非安全的并发的情况容易造成死锁若要高并发推荐使用ConcurrentHashMap这里的加了锁。 我们假设有二个进程T1、T2HashMap容量为2,T1线程放入key A、B、C、D、E。在T1线程中A、B、C Hash值相同于是形成一个链假设为A-C-B而D、E Hash值不同于是容量不足需要新建一个更大尺寸的hash表然后把数据从老的Hash表中 迁移到新的Hash表中(refresh)。这时T2进程闯进来了T1暂时挂起T2进程也准备放入新的key这时也 发现容量不足也refresh一把。refresh之后原来的链表结构假设为C-A之后T1进程继续执行链接结构 为A-C,这时就形成A.nextB,B.nextA的环形链表。一旦取值进入这个环形链表就会陷入死循环。 死锁是指两个或多个线程在执行过程中因争夺资源而造成的一种互相等待的现象若无外力作用它们都将无法向前推进。
HashMap 可能导致死锁的情况通常与以下因素有关
重入当一个线程在扩容rehashing过程中如果另一个线程尝试插入元素可能会触发新的扩容操作。如果多个线程同时进行这样的操作它们可能会相互等待对方释放锁从而导致死锁。并发修改如果多个线程同时尝试修改 HashMap 的结构如插入或删除元素而这些操作没有适当的同步控制就可能导致死锁。不当的迭代在多线程环境中如果一个线程在迭代 HashMap 的同时另一个线程修改了 HashMap可能会导致迭代器抛出 ConcurrentModificationException。虽然这通常不会导致死锁但如果迭代器的实现不当或者在处理异常时没有正确地同步也可能间接导致死锁。为了避免 HashMap 的死锁问题可以采取以下措施
使用 ConcurrentHashMap这是 Java 提供的一个线程安全的 HashMap 实现。它通过分段锁segmentation来允许并发的读写操作从而避免了死锁。同步包装可以使用 Collections.synchronizedMap 方法将 HashMap 包装为线程安全的 Map。但这种方式在高并发环境下性能可能不佳因为它对整个 Map 加锁而不是对单个元素。显式锁可以使用 ReentrantLock 或 synchronized 块来手动管理对 HashMap 的访问确保在修改 HashMap 时只有一个线程能够进行操作。不可变 Map如果不需要修改 Map可以使用 Collections.unmodifiableMap 创建一个不可修改的视图这样即使在多线程环境下也不会出现死锁。避免在循环中进行结构修改在循环中进行 HashMap 的结构修改如扩容可能会导致死锁应该避免这种情况。使用读写锁如果读操作远多于写操作可以考虑使用读写锁ReentrantReadWriteLock它允许多个读线程同时访问但写线程需要独占访问。
