• 天凉好个秋 置顶
    2018-05-24
    解决哈希冲突的常用方法有:

    开放定址法
    基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。

    再哈希法
    这种方法是同时构造多个不同的哈希函数:
    Hi=RH1(key)  i=1,2,…,k
    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    链地址法
    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    建立公共溢出区
    这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。
    展开
    
     118
  • 三口先生 置顶
    2018-05-24
    最常用的方法就是线性再散列。即插入元素时,没有发生冲突放在原有的规则下的空槽下,发生冲突时,简单遍历hash表,找到表中下一个空槽,进行元素插入。查找元素时,找到相应的位置的元素,如果不匹配则进行遍历hash表。
    然后就是我们非线性再散列,就是冲突时,再hash,核心思想是,如果产生冲突,产生一个新的hash值进行寻址,如果还是冲突,则继续。
    上述的方法,主要的缺点在于不能从表中删除元素。
    还有就是我们hashmap的思想外部拉链。
    
     13
  • 公号-云原生程序员
    2018-05-24
    Hashtable、HashMap、TreeMap心得

    三者均实现了Map接口,存储的内容是基于key-value的键值对映射,一个映射不能有重复的键,一个键最多只能映射一个值。

    (1)    元素特性
    HashTable中的key、value都不能为null;HashMap中的key、value可以为null,很显然只能有一个key为null的键值对,但是允许有多个值为null的键值对;TreeMap中当未实现 Comparator 接口时,key 不可以为null;当实现 Comparator 接口时,若未对null情况进行判断,则key不可以为null,反之亦然。

    (2)顺序特性
    HashTable、HashMap具有无序特性。TreeMap是利用红黑树来实现的(树中的每个节点的值,都会大于或等于它的左子树种的所有节点的值,并且小于或等于它的右子树中的所有节点的值),实现了SortMap接口,能够对保存的记录根据键进行排序。所以一般需要排序的情况下是选择TreeMap来进行,默认为升序排序方式(深度优先搜索),可自定义实现Comparator接口实现排序方式。

    (3)初始化与增长方式
    初始化时:HashTable在不指定容量的情况下的默认容量为11,且不要求底层数组的容量一定要为2的整数次幂;HashMap默认容量为16,且要求容量一定为2的整数次幂。
    扩容时:Hashtable将容量变为原来的2倍加1;HashMap扩容将容量变为原来的2倍。

    (4)线程安全性
    HashTable其方法函数都是同步的(采用synchronized修饰),不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性。也正因为如此,在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时,其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候,另外一个线程即使执行获取其他数据的操作也必须被阻塞,大大降低了程序的运行效率,在新版本中已被废弃,不推荐使用。
    HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步(1)可以用 Collections的synchronizedMap方法;(2)使用ConcurrentHashMap类,相较于HashTable锁住的是对象整体, ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升。

    (5)一段话HashMap
    HashMap基于哈希思想,实现对数据的读写。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时,它们会储存在同一个bucket位置的链表中,可通过键对象的equals()方法用来找到键值对。如果链表大小超过阈值(TREEIFY_THRESHOLD, 8),链表就会被改造为树形结构。
    展开
     1
     197
  • 清风
    2018-07-05
    感觉每个知识点都很重要,但又点到为止,感觉读完不痛不痒,好像学到什么,但细想又没掌握什么,希望能够深入一点!
     2
     190
  • amourling
    2018-07-11
    提个意见,文章中请不要出现太多似乎,怀疑之类的必须,该是什么就是什么,不确定的不要拿出来。
    
     104
  • 小飞哥 ‍超級會員
    2018-07-20
    总觉得还是不太深,只是每个map的区别。我觉得每个map的实现都能讲出很多问题来,在面试时也经常碰壁,看完但也没觉得学到什么深入的地方
     1
     43
  • Jerry银银
    2018-11-27
    为什么HashMap要树化?

    文章说『本质是个安全问题』,但是导致安全问题的本质其实是性能问题。哈希碰撞频繁,导致链表过长,查询时间陡升,黑客则会利用这个『漏洞』来攻击服务器,让服务器CPU被大量占用,从而引起了安全问题。 而树化(使用红黑树)能将时间复杂度降到O(logn),从而避免查询时间过长。所以说,本质还是个性能问题。

    ----------
    个人理解哈


    展开

    作者回复: 竟然无法反驳,哈哈

     2
     29
  • 鲤鱼
    2018-05-29
    读到最后链表树化刚准备开始飙车,结果突然跳车。树化讲细点更好

    作者回复: 感谢反馈,最近几章篇幅都超标了……只能照顾大多数需求,抱歉

    
     20
  • Darcy
    2018-07-28
    equals 的对称、反射、传递等特性。
    这里的反射是不是写错了,应该是自反性,对称性,传递性,一致性等等
    
     13
  • 睡骨
    2018-08-31
    希望作者分享源码的时候,最好备注是基于哪个版本的 毕竟有些地方不同版本差异较大
    
     10
  • 陈大麦
    2018-07-28
    老师我想问一下,hashmap明明继承了abstractmap,而abstractmap已经实现了map接口,为什么hashmap还要实现map接口呢?
     1
     10
  • j.c.
    2018-05-24
    这是面试必问题。什么时候也能讲讲红黑树的树化具体过程,那个旋转一直没搞懂。另外treeifyBin这个单词的词面意思是什么?
     1
     10
  • xinfangke
    2018-05-29
    老师 如果hashmap中不存在hash冲突 是不是就相当于一个数组结构呢 就不存在链表了呢

    作者回复: 我理解是

    
     9
  • Lh
    2019-02-20
    Hashtable、HashMap、TreeMap心得

    三者均实现了Map接口,存储的内容是基于key-value的键值对映射,一个映射不能有重复的键,一个键最多只能映射一个值。

    (1)    元素特性
    HashTable中的key、value都不能为null;HashMap中的key、value可以为null,很显然只能有一个key为null的键值对,但是允许有多个值为null的键值对;TreeMap中当未实现 Comparator 接口时,key 不可以为null;当实现 Comparator 接口时,若未对null情况进行判断,则key不可以为null,反之亦然。

    (2)顺序特性
    HashTable、HashMap具有无序特性。TreeMap是利用红黑树来实现的(树中的每个节点的值,都会大于或等于它的左子树种的所有节点的值,并且小于或等于它的右子树中的所有节点的值),实现了SortMap接口,能够对保存的记录根据键进行排序。所以一般需要排序的情况下是选择TreeMap来进行,默认为升序排序方式(深度优先搜索),可自定义实现Comparator接口实现排序方式。

    (3)初始化与增长方式
    初始化时:HashTable在不指定容量的情况下的默认容量为11,且不要求底层数组的容量一定要为2的整数次幂;HashMap默认容量为16,且要求容量一定为2的整数次幂。
    扩容时:Hashtable将容量变为原来的2倍加1;HashMap扩容将容量变为原来的2倍。

    (4)线程安全性
    HashTable其方法函数都是同步的(采用synchronized修饰),不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性。也正因为如此,在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时,其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候,另外一个线程即使执行获取其他数据的操作也必须被阻塞,大大降低了程序的运行效率,在新版本中已被废弃,不推荐使用。
    HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步(1)可以用 Collections的synchronizedMap方法;(2)使用ConcurrentHashMap类,相较于HashTable锁住的是对象整体, ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升。

    (5)一段话HashMap
    HashMap基于哈希思想,实现对数据的读写。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时,它们会储存在同一个bucket位置的链表中,可通过键对象的equals()方法用来找到键值对。如果链表大小超过阈值(TREEIFY_THRESHOLD, 8),链表就会被改造为树形结构。
    展开
    
     6
  • kevin
    2018-09-27
    看不太懂,讲的还不是不太浅显,既然是面试题,最好不要太浅,但也不要太深,你这个度掌握的不是很好

    作者回复: 嗯,谢谢指出

     1
     6
  • 鲸息
    2018-09-14
    为什么重写了 hashCode 也要重写 equals 呢?官方文档写的是重写了 equals 一定要重写 hashCode
     1
     6
  • coolboy
    2018-06-24
    removeEldestEntry这个方法是不是指移除最旧的对象,也就是按照最先被put进来的顺序,而不是指不常访问的对象。
    
     5
  • Jerry银银
    2018-05-24
    我一直认为:JAVA集合类是非常好的学习材料。

    如果敢说精通JAVA集合类,计算机功底肯定不会太差
    
     5
  • zjh
    2018-05-28
    受教了,把java集合的源代码掌握了,对java和数据结构的了解都会有很大的提升
    
     4
  • 代码狂徒
    2018-05-24
    针对负载因子,您所指的存太满会影响性能是指什么?毕竟已经开辟了相应内存空间的,没什么不用呢?

    作者回复: 冲突可能会增加,影响查询之类性能,当然看具体的需求

    
     4
我们在线,来聊聊吧