[单选题]
在这里帮大家总结一下hashMap和hashtable方面的知识点吧： 1. 关于HashMap的一些说法： a)
HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。HashMap的底层结构是一个数组，数组中的每一项是一条链表。
b) HashMap的实例有俩个参数影响其性能： “初始容量” 和 装填因子。 c) HashMap实现不同步，线程不安全。
HashTable线程安全 d) HashMap中的key-value都是存储在Entry中的。 e)
HashMap可以存null键和null值，不保证元素的顺序恒久不变，它的底层使用的是数组和链表，通过hashCode()方法和equals方法保证键的唯一性
f) 解决冲突主要有三种方法：定址法，拉链法，再散列法。HashMap是采用拉链法解决哈希冲突的。 注：
链表法是将相同hash值的对象组成一个链表放在hash值对应的槽位；
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。
沿此序列逐个单元地查找，直到找到给定
的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。
拉链法解决冲突的做法是： 将所有关键字为同义词的结点链接在同一个单链表中
。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数
组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。拉链法适合未规定元素的大小。
2. Hashtable和HashMap的区别： a) 继承不同。 public class
Hashtable extends Dictionary implements Map public class HashMap
extends AbstractMap implements Map b)
Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用Hashtable，但是要使用HashMap的话就要自己增加同步处理了。
c) Hashtable 中， key 和 value 都不允许出现 null 值。 在 HashMap 中， null
可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为 null 。当 get() 方法返回 null 值时，即可以表示 HashMap
中没有该键，也可以表示该键所对应的值为 null 。因此，在 HashMap 中不能由 get() 方法来判断 HashMap
中是否存在某个键， 而应该用 containsKey() 方法来判断。 d)
两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式
。 e) 哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。 f)
Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。
注： HashSet子类依靠hashCode()和equal()方法来区分重复元素。
HashSet内部使用Map保存数据，即将HashSet的数据作为Map的key值保存，这也是HashSet中元素不能重复的原因。而Map中保存key值的,会去判断当前Map中是否含有该Key对象，内部是先通过key的hashCode,确定有相同的hashCode之后，再通过equals方法判断是否相同。
发表于 2016-12-28 00:03:19
回复(75)
关注微信公众号：**************，
更多面试和实践总结干货等你来~
1. 开放定址法：线性探测再散列、二次探测再散列、再随机探测再散列；
2. 再哈希法：换一种哈希函数；
3. 链地址法 ：在数组中冲突元素后面拉一条链路，存储重复的元素；
4. 建立一个公共溢出区：其实就是建立一个表，存放那些冲突的元素。
什么时候会产生冲突
HashMap中调用 hashCode() 方法来计算hashCode。
由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产升。
HashMap底层是 数组和链表 的结合体。底层是一个线性数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。数组是 Entry[] 数组，静态内部类。 E ntry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用 next ，这就构成了链表。所以 很明显是链地址法。
具体过程：
当我们往HashMap中put元素的时候：当程序试图将一个key-value对放入HashMap中时，
1 . 程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置；
2 . 若 Entry 的存储位置上为 null ，直接存储该对象；若不为空，两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同，
3 . 循环遍历链表，如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖；如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部
关注微信公众号：**************
编辑于 2023-03-28 14:04:07
回复(15)
源码程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value
对。当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key
来计算并决定每个 Entry 的存储位置。Entry是数组，数组中的每个元素上挂这个一条链表。。
链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。很显然我们使用的不是开放地址法。
发表于 2015-08-16 13:35:10
回复(6)
1、开放定址法
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。
沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。
2 拉链法解决冲突的做法是：
将所有关键字为同义词的结点链接在同一个单链表中
。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数
组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。拉链法适合未规定元素的大小。
发表于 2016-03-21 21:13:52
回复(3)
HashMap存储原理：HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时，系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。
哈希冲突：HashMap判断当前确定的索引位置是否存在相同hashcode和相同key的元素，如果存在相同的hashcode和相同的key的元素，那么新值覆盖原来的旧值，并返回旧值。如果存在相同的hashcode，那么他们确定的索引位置就相同，这时判断他们的key是否相同，如果不相同，这时就是产生了hash冲突。
解决：Hash冲突后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。 如图：
Hashmap里面的bucket出现了单链表的形式，链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位。
发表于 2019-09-18 21:22:14
回复(0)
1.在Java 8 之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java 8中使用平衡树来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。
在Java 8中使用常量TREEIFY_THRESHOLD来控制是否切换到平衡树来存储。HashMap一开始使用链表，并在冲突的元素数量超过TREEIFY_THRESHOLD时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有，例如Hashtable和WeakHashMap。目前，这个常量值是8。
发表于 2018-03-30 10:08:17
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
