百度推广自己做网站吗,有网站公司源码可以重建网站吗,网址大全4399,谷歌翻译做多语言网站目录
✨探索Java基础 HashMap详解✨
总述
主体
1. HashMap的基本概念
2. HashMap的工作原理
3. HashMap的常用操作
4. HashMap的优缺点
总结
常见面试题
常见面试题解答
1. HashMap的底层实现原理是什么#xff1f;
2. 如何解决HashMap中的哈希冲突#xff1f;…目录
✨探索Java基础 HashMap详解✨
总述
主体
1. HashMap的基本概念
2. HashMap的工作原理
3. HashMap的常用操作
4. HashMap的优缺点
总结
常见面试题
常见面试题解答
1. HashMap的底层实现原理是什么
2. 如何解决HashMap中的哈希冲突
3. HashMap和Hashtable的区别是什么
4. 在什么情况下HashMap会发生扩容
5. 为什么HashMap不是线程安全的如何实现线程安全的HashMap
HashMap源码
1 put方法流程
2 扩容
3 get方法 ✨探索Java基础 HashMap详解✨
总述
在Java中HashMap 是一个常用的数据结构它实现了Map接口允许我们通过键值对的形式存储和快速查找数据。HashMap的底层是基于哈希表hash table的实现它的高效性和灵活性使其在各种编程场景中广受欢迎。本文将详细介绍HashMap的原理、使用方法、优缺点并提供一些常见的面试题。
主体
1. HashMap的基本概念 HashMap是一个散列表它存储键值对key-value pairs每个键对应一个唯一的值。HashMap不保证顺序并且允许null值作为键或值。
import java.util.HashMap;public class Main {public static void main(String[] args) {HashMapString, Integer map new HashMap();map.put(one, 1);map.put(two, 2);map.put(three, 3);System.out.println(map.get(one)); // 输出: 1}
}2. HashMap的工作原理
HashMap使用哈希表来存储数据。键的哈希值通过hash()方法计算然后通过哈希函数将哈希值映射到数组的索引位置上。通过链地址法chaining来解决哈希冲突即在每个数组索引处存储一个链表Java 8及之后版本采用红黑树以提高性能。
public int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}3. HashMap的常用操作 添加元素 使用put()方法。 map.put(four, 4); 获取元素 使用get()方法。 int value map.get(two); 移除元素 使用remove()方法。 map.remove(three); 遍历元素 for (Map.EntryString, Integer entry : map.entrySet()) {System.out.println(entry.getKey() : entry.getValue());
}4. HashMap的优缺点
优点
快速查找 平均时间复杂度为O(1)。灵活 可以存储不同类型的对象允许null键和值。
缺点
非线程安全 多线程情况下需要手动同步。不保证顺序 插入顺序和遍历顺序可能不同。 总结
HashMap是Java中一个强大且高效的集合类用于快速查找和存储键值对。理解其工作原理和常用操作对于提高编程效率和解决复杂问题非常有帮助。 常见面试题
HashMap的底层实现原理是什么如何解决HashMap中的哈希冲突HashMap和Hashtable的区别是什么在什么情况下HashMap会发生扩容为什么HashMap不是线程安全的如何实现线程安全的HashMap
常见面试题解答
1. HashMap的底层实现原理是什么
HashMap的底层是基于哈希表hash table实现的。它内部使用一个数组来存储元素每个数组的元素被称为“桶”bucket。当我们向HashMap中插入一个键值对时会先根据键的hashCode()方法计算出哈希值然后通过哈希函数将哈希值映射到数组的索引位置上。HashMap通过链地址法chaining来解决哈希冲突即每个桶中存储一个链表Java 8及之后版本采用红黑树以提高性能。
public int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}2. 如何解决HashMap中的哈希冲突
HashMap采用链地址法chaining来解决哈希冲突。具体方法是每个桶中存储一个链表或者在Java 8及之后版本中当链表长度超过一定阈值时会转换成红黑树所有映射到同一索引位置的键值对都会存储在这个链表或红黑树中。
当插入一个新的键值对时如果该键值对的哈希值映射到的索引位置已经存在其它元素则会将新的键值对添加到该位置的链表或红黑树中。
3. HashMap和Hashtable的区别是什么
线程安全性 Hashtable是线程安全的所有方法都是同步的而HashMap不是线程安全的适用于单线程环境或通过外部同步来保证线程安全。null键和值 HashMap允许一个null键和多个null值而Hashtable不允许null键和值。性能 由于Hashtable的方法是同步的因此在单线程环境下性能比HashMap差。遗产 Hashtable是基于较老的Dictionary类实现的而HashMap是从Java 1.2开始作为Map接口的实现类。
4. 在什么情况下HashMap会发生扩容 HashMap会在容量达到阈值默认是当前容量的0.75倍时发生扩容。扩容时HashMap的容量会变为原来的两倍并重新哈希已有的键值对重新分配到新的桶中。扩容可以避免哈希冲突保持HashMap的高效性。
5. 为什么HashMap不是线程安全的如何实现线程安全的HashMap
HashMap不是线程安全的因为它的所有方法都不是同步的。在多线程环境下多个线程同时修改HashMap的结构可能导致数据不一致或出现死循环。
要实现线程安全的HashMap可以通过以下方法 使用Collections.synchronizedMap(MapK, V m)方法 这个方法返回一个线程安全的Map。 MapString, Integer synchronizedMap Collections.synchronizedMap(new HashMap()); 使用ConcurrentHashMap 这是Java提供的线程安全的Map实现适用于高并发环境。它通过分段锁机制Segmented Locking来提高并发性能。 ConcurrentHashMapString, Integer concurrentMap new ConcurrentHashMap();
HashMap源码
1 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) {NodeK,V[] tab; NodeK,V p; int n, i;//判断数组是否未初始化if ((tab table) null || (n tab.length) 0)//如果未初始化调用resize方法 进行初始化n (tab resize()).length;//通过 运算求出该数据key的数组下标并判断该下标位置是否有数据if ((p tab[i (n - 1) hash]) null)//如果没有直接将数据放在该下标位置tab[i] newNode(hash, key, value, null);//该数组下标有数据的情况else {NodeK,V e; K k;//判断该位置数据的key和新来的数据是否一样if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))//如果一样证明为修改操作该节点的数据赋值给e,后边会用到e p;//判断是不是红黑树else if (p instanceof TreeNode)//如果是红黑树的话进行红黑树的操作e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);//新数据和当前数组既不相同也不是红黑树节点证明是链表else {//遍历链表for (int binCount 0; ; binCount) {//判断next节点如果为空的话证明遍历到链表尾部了if ((e p.next) null) {//把新值放入链表尾部p.next newNode(hash, key, value, null);//因为新插入了一条数据所以判断链表长度是不是大于等于8if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st//如果是进行转换红黑树操作treeifyBin(tab, hash);break;}//判断链表当中有数据相同的值如果一样证明为修改操作if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;//把下一个节点赋值为当前节点p e;}}//判断e是否为空e值为修改操作存放原数据的变量if (e ! null) { // existing mapping for key//不为空的话证明是修改操作取出老值V oldValue e.value;//一定会执行 onlyIfAbsent传进来的是falseif (!onlyIfAbsent || oldValue null)//将新值赋值当前节点e.value value;afterNodeAccess(e);//返回老值return oldValue;}}//计数器计算当前节点的修改次数modCount;//当前数组中的数据数量如果大于扩容阈值if (size threshold)//进行扩容操作resize();//空方法afterNodeInsertion(evict);//添加操作时 返回空值return null;
}
2 扩容
//扩容、初始化数组
final NodeK,V[] resize() {NodeK,V[] oldTab table;//如果当前数组为null的时候把oldCap老数组容量设置为0int oldCap (oldTab null) ? 0 : oldTab.length;//老的扩容阈值int oldThr threshold;int newCap, newThr 0;//判断数组容量是否大于0大于0说明数组已经初始化if (oldCap 0) {//判断当前数组长度是否大于最大数组长度if (oldCap MAXIMUM_CAPACITY) {//如果是将扩容阈值直接设置为int类型的最大数值并直接返回threshold Integer.MAX_VALUE;return oldTab;}//如果在最大长度范围内则需要扩容 OldCap 1等价于oldCap*2//运算过后判断是不是最大值并且oldCap需要大于16else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold 等价于oldThr*2}//如果oldCap0但是已经初始化了像把元素删除完之后的情况那么它的临界值肯定还存在 如果是首次初始化它的临界值则为0else 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);}//初始化容量小于16的时候扩容阈值是没有赋值的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;//判断当前下标为j的数组如果不为空的话赋值个e进行下一步操作if ((e oldTab[j]) ! null) {//将数组位置置空oldTab[j] null;//判断是否有下个节点if (e.next null)//如果没有就重新计算在新数组中的下标并放进去newTab[e.hash (newCap - 1)] e;//有下个节点的情况并且判断是否已经树化else if (e instanceof TreeNode)//进行红黑树的操作((TreeNodeK,V)e).split(this, newTab, j, oldCap);//有下个节点的情况并且没有树化链表形式else {//比如老数组容量是16那下标就为0-15//扩容操作*2容量就变为32下标为0-31//低位0-15高位16-31//定义了四个变量// 低位头 低位尾NodeK,V loHead null, loTail null;// 高位头 高位尾NodeK,V hiHead null, hiTail null;//下个节点NodeK,V next;//循环遍历do {//取出next节点next e.next;//通过 与操作 计算得出结果为0if ((e.hash oldCap) 0) {//如果低位尾为null证明当前数组位置为空没有任何数据if (loTail null)//将e值放入低位头loHead e;//低位尾不为null证明已经有数据了else//将数据放入next节点loTail.next e;//记录低位尾数据loTail e;}//通过 与操作 计算得出结果不为0else {//如果高位尾为null证明当前数组位置为空没有任何数据if (hiTail null)//将e值放入高位头hiHead e;//高位尾不为null证明已经有数据了else//将数据放入next节点hiTail.next e;//记录高位尾数据hiTail e;}} //如果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;}
3 get方法
public V get(Object key) {NodeK,V e;//hash(key)获取key的hash值//调用getNode方法见下面方法return (e getNode(hash(key), key)) null ? null : e.value;
}final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;//找到key对应的桶下标赋值给first节点if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {//判断hash值和key是否相等如果是则直接返回桶中只有一个数据大部分的情况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;
} 觉得有用的话可以点点赞 (*/ω*)支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
