CS_BLOG
0%

Map

Posted on Edited on In ,
9.2k

如何对map进行快速遍历？

  • 使用 for-each 循环和 entrySet () 方法：这是一种较为常见和简洁的遍历方式，它可以同时获取 Map 中的键和值
  • 使用 for-each 循环和 keySet () 方法：如果只需要遍历 Map 中的键，可以使用 keySet () 方法，这种方式相对简单，性能也较好。
  • 使用迭代器：通过获取 Map 的 entrySet () 或 keySet () 的迭代器，也可以实现对 Map 的遍历，这种方式在需要删除元素等操作时比较有用。
  • 使用 Lambda 表达式和 forEach () 方法：在 Java 8 及以上版本中，可以使用 Lambda 表达式和 forEach () 方法来遍历 Map，这种方式更加简洁和函数式。
  • 使用 Stream API：Java 8 引入的 Stream API 也可以用于遍历 Map，可以将 Map 转换为流，然后进行各种操作。

HashMap实现原理介绍一下？

在 JDK 1.7版本之前，HashMap数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。

所以在 JDK 1.8版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n），可以提高查询性能，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

了解的哈希冲突解决方法有哪些？

  • 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
  • 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
  • 再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
  • 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap是线程安全的吗？

Hashmap不是线程安全的，Hashmap在多线程会存在下面的问题：

  • JDK 1.7 HashMap 采用数组 + 链表的数据结构，多线程背景下，在数组扩容的时候，存在 Entry 链死循环和数据丢失问题。
  • JDK 1.8 HashMap 采用数组 + 链表 + 红黑二叉树的数据结构，优化了 1.7 中数组扩容的方案，解决了Entry 链死循环和数据丢失问题。但是多线程背景下，put 方法存在数据覆盖的问题。

如果要保证线程安全，可以通过这些方法来保证：

  • 多线程环境可以使用Collections.synchronizedMap同步加锁的方式，还可以使用HashTable，但是同步的方式显然性能不达标，而ConurrentHashMap更适合高并发场景使用。
  • ConcurrentHashmap在JDK1.7和1.8的版本改动比较大，1.7使用Segment+HashEntry分段锁的方式实现，1.8则抛弃了Seg ment，改为使用CAS+synchronized+Node实现，同样也加入了红黑树，避免链表过长导致性能的问题。

hashmap 调用get方法一定安全吗？

不是，调用get方法有几点需要注意的地方：

  • 空指针异常：如果你尝试用 null 作为键调用 get 方法，而 HashMap 没有被初始化（即为 null），那么会抛出空指针异常。不过，如果 HashMap 已经初始化，使用 null 作为键是允许的，因为 HashMap 支持 null 键。
  • 线程安全：HashMap 本身不是线程安全的。如果在多线程环境中，没有适当的同步措施，同时对 HashMap 进行读写操作可能会导致不可预测的行为。例如，在一个线程中调用 get 方法读取数据，而另一个线程同时修改了结构（如增加或删除元素），可能会导致读取操作得到错误的结果或抛出 ConcurrentModificationException。如果需要在多线程环境中使用类似 HashMap 的数据结构，可以考虑使用 ConcurrentHashMap。

HashMap一般用什么做Key？为啥String适合做Key呢？

用 string做 key，因为 String对象是不可变的，一旦创建就不能被修改，这确保了Key的稳定性。如果Key是可变的，可能会导致hashCode和equals方法的不一致，进而影响HashMap的正确性。

为什么HashMap要用红黑树而不是平衡二叉树？

  • 平衡二叉树追求的是一种“完全平衡”状态：任何结点的左右子树的高度差不会超过 1，优势是树的结点是很平均分配的。这个要求实在是太平了，导致每次进行插入/删除结点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
  • 红黑树不追求这种完全平衡状态，而是追求一种“弱平衡”状态：整个树最长路径不会超过最短路径的2倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整，这也是我们为什么大多数情况下使用红黑树的原因。

Hashmap的put过程介绍一下

  • 第一步：根据要添加的键的哈希码计算在数组中的位置（索引）。

  • 第二步：检查该位置是否为空（即没有键值对存在）

    • 如果为空，则直接在该位置创建一个新的Entry对象来存储键值对。将要添加的键值对作为该Entry的键和值，并保存在数组的对应位置。将HashMap的修改次数（modCount）加1，以便在进行迭代时发现并发修改。

  • 第三步：如果该位置已经存在其他键值对，检查该位置的第一个键值对的哈希码和键是否与要添加的键值对相同？

    • 如果相同，则表示找到了相同的键，直接将新的值替换旧的值，完成更新操作。

  • 第四步：如果第一个键值对的哈希码和键不相同，则需要遍历链表或
    红黑树来查找是否有相同的键    ：

    • 如果键值对集合是链表结构，从链表的头部开始逐个比较键的哈希码和equals()方法，直到找到相同的键或达到链表末尾。
      • 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
      • 如果没有找到相同的键，则将新的键值对添加到链表的头部。
    • 如果键值对集合是红黑树结构，在红黑树中使用哈希码和equals()方法进行查找。根据键的哈希码，定位到红黑树中的某个节点，然后逐个比较键，直到找到相同的键或达到红黑树末尾。
      • 如果找到了相同的键，则使用新的值取代旧的值，即更新键对应的值。
      • 如果没有找到相同的键，则将新的键值对添加到红黑树中。

  • 第五步：检查链表长度是否达到阈值（默认为8）：

    • 如果链表长度超过阈值，且HashMap的数组长度大于等于64，则会将链表转换为红黑树，以提高查询效率。

  • 第六步：检查负载因子是否超过阈值（默认为0.75）：

    • 如果键值对的数量（size）与数组的长度的比值大于阈值，则需要进行扩容操作。

  • 第七步：扩容操作：

    • 创建一个新的两倍大小的数组。
    • 将旧数组中的键值对重新计算哈希码并分配到新数组中的位置。
    • 更新HashMap的数组引用和阈值参数。

  • 第八步：完成添加操作。

此外，HashMap是非线程安全的，如果在多线程环境下使用，需要采取额外的同步措施或使用线程安全的ConcurrentHashMap。

HashMap 的 put (key,val) 和 get (key) 过程

  • 存储对象时，我们将 K/V 传给 put 方法时，它调用 hashCode 计算 hash 从而得到 bucket 位置，进一步存储，HashMap 会根据当前 bucket 的占用情况自动调整容量 (超过 Load Facotr 则 resize 为原来的 2 倍)。
  • 获取对象时，我们将 K 传给 get，它调用 hashCode 计算 hash 从而得到 bucket 位置，并进一步调用 equals () 方法确定键值对。如果发生碰撞的时候，Hashmap 通过链表将产生碰撞冲突的元素组织起来，在 Java 8 中，如果一个 bucket 中碰撞冲突的元素超过某个限制 (默认是 8)，则使用红黑树来替换链表，从而提高速度。

hashmap key可以为null吗？

可以为 null。

  • hashMap中使用hash()方法来计算key的哈希值，当key为空时，直接令key的哈希值为0，不走key.hashCode()方法；

  • hashMap虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；

  • 因为hashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。

重写HashMap的equal和hashcode方法需要注意什么？

HashMap使用Key对象的hashCode()和equals方法去决定key-value对的索引。当我们试着从HashMap中取值的时候，这些方法也会被用到。如果这些方法没有被正确地实现，在这种情况下，两个不同Key也许会产生相同的hashCode()和equals()输出，HashMap将会认为它们是相同的，然后覆盖它们，而非把它们存储到不同的地方。

同样的，所有不允许存储重复数据的集合类都使用hashCode()和equals()去查找重复，所以正确实现它们非常重要。equals()和hashCode()的实现应该遵循以下规则：

  • 如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
  • 如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

重写HashMap的equal方法不当会出现什么问题？

HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。

所以 equals相等的两个对象，hashCode一定相等。hashCode相等的两个对象，equals不一定相等（比如散列冲突的情况）

重写了equals方法，不重写hashCode方法时，可能会出现equals方法返回为true，而hashCode方法却返回false，这样的一个后果会导致在hashmap等类中存储多个一模一样的对象，导致出现覆盖存储的数据的问题，这与hashmap只能有唯一的key的规范不符合。

列举 HashMap 在多线程下可能会出现的问题？

  • JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
  • 多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。

HashMap 的扩容机制介绍一下

hashMap 默认的负载因子是 0.75，即如果 hashmap 中的元素个数超过了总容量 75%，则会触发扩容，扩容分为两个步骤：

  • 第 1 步是对哈希表长度的扩展（2 倍）
  • 第 2 步是将旧哈希表中的数据放到新的哈希表中。

因为我们使用的是 2 次幂的扩展 (指长度扩为原来 2 倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2 次幂的位置。

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

这个设计既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

HashMap的大小为什么是2的n次方大小呢？

在JDK1.7中，HashMap整个扩容过程就是分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的hash值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。

而在JDK 1.8中，HashMap对扩容操作做了优化。由于扩容数组的长度是2倍关系，所以对于假设初始tableSize = 4要扩容到8来说就是0100到1000的变化（左移一位就是2倍），在扩容中只用判断原来的hash值和左移动的一位（newtable的值）按位与操作是0或1就行，0的话索引不变，1的话索引变成原索引加上扩容前数组。

之所以能通过这种“与运算”来重新分配索引，是因为hash值本来就是随机的，而hash按位与上newTable得到的0（扩容前的索引位置）和1（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

往hashmap存20个元素，会扩容几次？

当插入20个元素时，HashMap的扩容过程如下：
初始容量：16

  • 插入第1到第12个元素时，不需要扩容。
  • 插入第13个元素时，达到负载因子限制，需要扩容。此时，HashMap的容量从16扩容到32。

扩容后的容量：32

  • 插入第14到第24个元素时，不需要扩容。

因此，总共会进行一次扩容。

说说hashmap的负载因子

HashMap负载因子loadFactor的默认值是0.75，当HashMap中的元素个数超过了容量的75%时，就会进行扩容。

负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75的负载因子在这两个因素之间取得了良好的平衡。

HashMap和Hashtable有什么不一样的？HashMap一般怎么用？

  • HashMap线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
  • HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
  • 怎么用：HashMap主要用来存储键值对，可以调用put方法向其中加入元素，调用get方法获取某个键对应的值，也可以通过containsKey方法查看某个键是否存在等

ConcurrentHashMap 怎么实现的？

JDK 1.7 ConcurrentHashMap

在 JDK 1.7 中它使用的是数组加链表的形式实现的，而数组又分为：大数组 Segment 和小数组 HashEntry。Segment 是一种可重入锁（ReentrantLock），在 ConcurrentHashMap 里扮演锁的角色；HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素。
JDK 1.7 ConcurrentHashMap 分段锁技术将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK 1.8 ConcurrentHashMap

JDK 1.8 ConcurrentHashMap 主要通过 volatile + CAS 或者 synchronized 来实现的线程安全的。添加元素时首先会判断容器是否为空：

  • 如果为空则使用 volatile 加 CAS 来初始化
  • 如果容器不为空，则根据存储的元素计算该位置是否为空。
    • 如果根据存储的元素计算结果为空，则利用 CAS 设置该节点；
    • 如果根据存储的元素计算结果不为空，则使用 synchronized，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

如果把上面的执行用一句话归纳的话，就相当于是ConcurrentHashMap通过对头结点加锁来保证线程安全的，锁的粒度相比 Segment 来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。

而且 JDK 1.8 使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的 O(n) 优化到了 O(logn) 的时间复杂度。

分段锁怎么加锁的？

在ConcurrentHashMap中，将整个数据结构分为多个Segment，每个Segment都类似于一个小的HashMap，每个Segment都有自己的锁，不同Segment之间的操作互不影响，从而提高并发性。

在ConcurrentHashMap中，对于插入、更新、删除等操作，需要先定位到具体的Segment，然后再在该Segment上加锁，而不是像传统的HashMap一样对整个数据结构加锁。这样可以使得不同Segment之间的操作并行进行，提高了并发性能。

分段锁是可重入的吗？

JDK 1.7 ConcurrentHashMap中的分段锁是用了ReentrantLock，是一个可重入的锁。

已经用了synchronized，为什么还要用CAS呢？

ConcurrentHashMap使用这两种手段来保证线程安全主要是一种权衡的考虑，在某些操作中使用synchronized，还是使用CAS，主要是根据锁竞争程度来判断的。

比如：在putVal中，如果计算出来的hash槽没有存放元素，那么就可以直接使用CAS来进行设置值，这是因为在设置元素的时候，因为hash值经过了各种扰动后，造成hash碰撞的几率较低，那么我们可以预测使用较少的自旋来完成具体的hash槽操作。

当发生了hash碰撞的时候说明容量不够用了或者已经有大量线程访问了，因此这时候使用synchronized来处理hash碰撞比CAS效率要高，因为发生了hash碰撞大概率来说是线程竞争比较强烈。

ConcurrentHashMap用了悲观锁还是乐观锁?

悲观锁和乐观锁都有用到。

添加元素时首先会判断容器是否为空：

  • 如果为空则使用volatile加CAS（乐观锁）来初始化。
  • 如果容器不为空，则根据存储的元素计算该位置是否为空。
  • 如果根据存储的元素计算结果为空，则利用CAS（乐观锁）设置该节点；
  • 如果根据存储的元素计算结果不为空，则使用synchronized（悲观锁），然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。

HashTable 底层实现原理是什么？

  • Hashtable的底层数据结构主要是数组加上链表，数组是主体，链表是解决hash冲突存在的。
  • HashTable是线程安全的，实现方式是Hashtable的所有公共方法均采用synchronized关键字，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

HashTable 线程安全是怎么实现的？

因为它的 put，get 做成了同步方法，保证了 Hashtable 的线程安全性，每个操作数据的方法都进行同步控制之后，由此带来的问题任何一个时刻只能有一个线程可以操纵 Hashtable，所以其效率比较低。

在 Java 中，可以使用 synchronized 关键字来标记一个方法或者代码块，当某个线程调用该对象的 synchronized 方法或者访问 synchronized 代码块时，这个线程便获得了该对象的锁，其他线程暂时无法访问这个方法，只有等待这个方法执行完毕或者代码块执行完毕，这个线程才会释放该对象的锁，其他线程才能执行这个方法或者代码块。

hashtable 和concurrentHashMap有什么区别

底层数据结构

  • jdk7之前的ConcurrentHashMap底层采用的是分段的数组+链表实现，jdk8之后采用的是数组+链表/红黑树；
  • HashTable采用的是数组+链表，数组是主体，链表是解决hash冲突存在的。

实现线程安全的方式

  • jdk8以前，ConcurrentHashMap采用分段锁，对整个数组进行了分段分割，每一把锁只锁容器里的一部分数据，多线程访问不同数据段里的数据，就不会存在锁竞争，提高了并发访问；jdk8以后，直接采用数组+链表/红黑树，并发控制使用CAS和synchronized操作，更加提高了速度。
  • HashTable：所有的方法都加了锁来保证线程安全，但是效率非常的低下，当一个线程访问同步方法，另一个线程也访问的时候，就会陷入阻塞或者轮询的状态。

说一下HashMap和Hashtable、ConcurrentMap的区别

  • HashMap：线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
  • HashTable：线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
  • ConcurrentHashMap：是Java中的一个线程安全的哈希表实现，它可以在多线程环境下并发地进行读写操作，而不需要像传统的HashTable那样在读写时加锁。ConcurrentHashMap的实现原理主要基于分段锁和CAS操作。它将整个哈希表分成了多Segment（段），每个Segment都类似于一个小的HashMap，它拥有自己的数组和一个独立的锁。在ConcurrentHashMap中，读操作不需要锁，可以直接对Segment进行读取，而写操作则只需要锁定对应的Segment，而不是整个哈希表，这样可以大大提高并发性能。