hashCode
相同,且任一一个调用equals
方法与另一个返回true
,即认为两个对象等同。HashMap
中有如下几个量需要注意,代码如下:HashMap
和HashTable
的区别HashMap
是非线程安全的,而HashTable
则是线程安全的,也因此,HashMap
的效率较高。除此之外,在HashMap
中null
可以用来作为键,而HashTable
则不可以,否则抛出NullPointerException
。HashMap
和HashSet
的区别HashSet
底层基于HashMap
实现,其实现了Set
接口,仅用来存储对象而不是键值对。而且HashSet
较HashMap
效率低。HashMap
的长度为什么是2的幂次方put
方法的源代码:putVal
方法中,我们直接来看putVal
的代码:afterNodeAccess
和afterNodeInsertion
这两个方法在HashMap
里面的实现是空的,在此处什么都不做,其注释中写道:Callbacks to allow LinkedHashMap
post-actions,即适用于LinkedHashMap
实现一些后置功能的回调函数。put
方法为什么线程不安全HashMap
不是线程安全的,多线程的情况下操作HashMap
的put
操作有可能导致死循环,原因在于HashMap
扩容使用的resize
方法,由于扩容是新建一个数组,然后复制原数据到数组,由于数组下标挂有链表,所以需要复制链表,但多线程操作有可能导致环形链表。HashMap
实现中的transfer
方法:resize
之前Entry
数组的结构如下:e
和next
实际上都为引用类型变量。线程A继续操作,线程A的newTable
变为了如下状态:e=3
于是又再一次进入循环:newTable[3]
中所保存的链表即成了循环链表,当查找一个元素,假设说8,经计算indexOf(8) = 3
,那么将会在table[3]
所存储链表中查找,此时get(8)
操作即为一个死循环。put
方法为什么线程不安全?HashMap
依旧是线程不安全的,因为写入丢失。HashMap
中插入元素,而这两个元素恰好又有相同的hash值,假设这个hash值所对应的数组下标所在位置原先是没有元素的,那线程1直接进行赋值,然后CPU切换到了线程2,线程2又进行了一次直接复制,线程2赋的值覆盖了线程1的值,导致了写入丢失的问题。HashMap
插入元素时,需要进行扩容操作的话,线程1和线程2都会各自生成各自的newTab
,然后最后tab = resize()
,到最后table
里面只保存了最后一个线程的newTab
,其余线程的均会丢失。get
方法:getNode
方法中,用于通过键值hash
和键值对象获取Node
,如果其得到的值为null
那就返回null
,否则返回Node
对象的value
,我们着重来看getNode
方法:remove
方法用于从HashMap
中移除一个元素,代码如下:removeNode
中,我们来看其源代码:(e.hash & oldCap) == 0
的理解e.hash & (n - 1)
,当n翻一番的时候,这个产生的结果只可能出现2种情况,一种是不变,如下:n-1
的值,在上例中,扩容前后的这个元素在数组中的位置依旧保持不变oldCap
。oldCap
(n)的位置,如下:hash & n
是否等于1就可以判断出扩容之后的位置是否发生变化来,由此判断条件(e.hash & oldCap) == 0
的意思即为判断扩容后的位置是否发生变化。hashCode
有着直接的关联,这就产生了一个问题,首先hashCode
的返回值是依据当前对象在JVM中的内存地址算出来的,当我们用一个自定义类的对象来做key
的话,同样内容的两个对象,get
操作就会出现问题,看代码:get
函数会返回null
,someone
和boy
虽说看上去内容是一样的,但是实际上是两个对象,二者的hashCode
会返回不一样的值,所得到的用于查找的hash码值也会不一样,所以get
失败。好,我们来重写一下Person
类的hashCode
让他由属性name
和age
来决定,代码如下:TL;DRString
类型的对象所产生的hashCode
值是由其所保存的字符串决定的,字符串相同,hashCode
值也相同,字符串不同,hashCode
值也不同。我们可以在其文档中,找到相关hashCode
值产生算法的描述:1s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]Copied!
Person
对象产生的hashCode
也相同了,让我们重新运行代码,依旧输出null
,经检查发现get
函数不仅会判断key
的hash值相同,同时也会使用equals
函数来判断两个对象是否等同,重写equals
函数如下:HashMap
时,get
操作会先通过hashCode
计算其相关的hash
码值,当这个hash
码值相同时,会调用equals
方法来检验当前对象与数组中hash
码值相同的对象是否等同,如果等同即会返回其关联的value
。Ideally, under randomhashCodes
, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) pow(0.5, k) / factorial(k)). The first values are: 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million