Java中，在HashMap可以用put(Key, Value)添加元素， 如何在LinkedHashMap中添加（Key, Value）？

和HashMap方法一样，也是用put添加元素，LinkedHashMap也是java.util.Map的实现类

区别在于

Hashmap 是一个最常用的Map,它根据键的HashCode值存储数据,根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。 HashMap最多只允许一条记录的键为Null允许多条记录的值为 NullHashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的.也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序,默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。

(1)存储键值对，实现快速存取数据；

(2)允许键/值为null，但不允许重复的键；

(3)非同步synchronized(比同步快)，线程不安全；

注：让HashMap同步： Map m = Collections.synchronizeMap(hashMap)

(4)实现Map接口，对键值对进行映射，不保证有序(比如插入的顺序)

注：Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。

(5)HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”

(6)HashMap添加元素时，是使用自定义的哈希算法

(1)不存储键值对，仅存储对象；

(2)不允许键/值为null；

(3)线程安全(速度慢)，采用synchronize关键字加锁原理(几乎在每个方法上都加锁)，；

(4)实现了Set接口，不允许集合中有重复的值。注：将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，

比较对象的值是否相等，以确保set中没有储存相等的对象。hashCode()可能相同，用equals()判断对象的相等性。

(5)Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；

(6)Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

(1)Java并发包java.util.concurrent中的一个线程安全且高效的HashMap实现

(2)不允许键/值为null；

(3)线程安全：在JDK1.7中采用“分段锁”的方式，1.8中直接采用了CAS（无锁算法）+ synchronized。

Entry：HashMap是一个用于存储Key-Value键值对的集合，每一个键值对叫做Entry，这些Entry分散存储在一个数组当中。

hashMap是在bucket中储存键对象和值对象，作为Map.Entry

bucket：HashMap初始化时，创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置被称为“桶(bucket)”，

每个bucket都有其指定索引，系统可以根据其索引快速访问该bucket里存储的元素。

loadFactor：负载因子。默认值DEFAULT_LOAD_FACTOR = 0.75f；

capacity：容量，指的是数组的长度

threshold：阈值=capacity*loadFactor。超过阈值则扩容为原来的两倍。

size：HashMap的大小，它是HashMap保存的键值对的数量。

HashMap是基于hashing的原理，底层使用哈希表结构(数组+链表)实现。使用put(key,value)存储对象，使用get(key)获取对象。

理解为，数组中存储的是一个Entry，并且作为链表头结点，头结点之后的每个节点中储存键值对对象Entry。

给put()方法传递键和值时，先对键调用hashCode()方法计算hash从而得到bucket位置，进一步存储，

HashMap会根据当前bucket的占用情况自动调整容量(超过负载因子Load Facotr则resize为原来的2倍)。

扩容扩的是数组的容量，发生碰撞后当链表长度到达8后，链表上升为红黑树，提高速度。

根据键key的hashcode找到bucket位置，然后遍历链表节点，调用equals(用来获取值对象)方法确定键值对，找到要找的值对象。

a.对key的hashCode做hash *** 作(高16bit不变，低16bit和高16bit做了一个异或)

b.计算下标(n-1) &hash，从而获得buckets的位置 //h &(length-1)

数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法。

其他解决hash冲突办法：开放定址法、链地址法、再哈希法。

根据hashcode来划分的数组，如果数组的坐标相同，则进入链表这个数据结构中，jdk1.7及以前为头插法，jdk1.8之后是尾插法，

在jdk1.8之后，当链表长度到达8的时候，jdk1.8上升为红黑树。存的时候按照上面的方式存，取的时候根据equals确定值对象。

1.常见问题：集合类、数据结构、线程安全、解决碰撞方法、hashing概念和方法、equals()和hashCode()的应用、不可变对象的好处

https://blog.csdn.net/weixin_42636552/article/details/82016183

https://blog.csdn.net/u012512634/article/details/72735183

https://blog.csdn.net/zaimeiyeshicengjing/article/details/81589953

https://blog.csdn.net/aura521521/article/details/78462459

对于包含容器类型的程序设计语言来说，基本上都会涉及到hashCode。在Java中也一样，hashCode方法的主要作用是为了配合基于散列的集合一起正常运行，这样的散列集合包括HashSet、HashMap以及HashTable。

为什么这么说呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？（注意：集合中不允许重复的元素存在）

也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值， 就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了，说通俗一点：Java中的hashCode方法就是根据一定的规则将与对象相关的信息（比如对象的存储地址，对象的字段等）映射成一个数值，这个数值称作为散列值。下面这段代码是java.util.HashMap的中put方法的具体实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

public V put(K key, V value) {

if (key == null)

return putForNullKey(value)

int hash = hash(key.hashCode())

int i = indexFor(hash, table.length)

for (Entry<K,V>e = table[i]e != nulle = e.next) {

Object k

if (e.hash == hash &&((k = e.key) == key || key.equals(k))) {

V oldValue = e.value

e.value = value

e.recordAccess(this)

return oldValue

}

}

modCount++

addEntry(hash, key, value, i)

return null

}

put方法是用来向HashMap中添加新的元素，从put方法的具体实现可知，会先调用hashCode方法得到该元素的hashCode值，然后查看table中是否存在该hashCode值，如果存在则调用equals方法重新确定是否存在该元素，如果存在，则更新value值，否则将新的元素添加到HashMap中。从这里可以看出，hashCode方法的存在是为了减少equals方法的调用次数，从而提高程序效率。

如果对于hash表这个数据结构的朋友不清楚，可以参考这几篇博文

http://www.cnblogs.com/jiewei915/archive/2010/08/09/1796042.html

http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html

http://www.java3z.com/cwbwebhome/article/article8/83560.html?id=4649

有些朋友误以为默认情况下，hashCode返回的就是对象的存储地址，事实上这种看法是不全面的，确实有些JVM在实现时是直接返回对象的存储地址，但是大多时候并不是这样，只能说可能存储地址有一定关联。下面是HotSpot JVM中生成hash散列值的实现：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

static inline intptr_t get_next_hash(Thread * Self, oop obj) {

intptr_t value = 0

if (hashCode == 0) {

// This form uses an unguarded global Park-Miller RNG,

// so it's possible for two threads to race and generate the same RNG.

// On MP system we'll have lots of RW access to a global, so the

// mechanism induces lots of coherency traffic.

value = os::random()

} else

if (hashCode == 1) {

// This variation has the property of being stable (idempotent)

// between STW operations. This can be useful in some of the 1-0

// synchronization schemes.

intptr_t addrBits = intptr_t(obj) >>3

value = addrBits ^ (addrBits >>5) ^ GVars.stwRandom

} else

if (hashCode == 2) {

value = 1// for sensitivity testing

} else

if (hashCode == 3) {

value = ++GVars.hcSequence

} else

if (hashCode == 4) {

value = intptr_t(obj)

} else {

// Marsaglia's xor-shift scheme with thread-specific state

// This is probably the best overall implementation -- we'll

// likely make this the default in future releases.

unsigned t = Self->_hashStateX

t ^= (t <<11)

Self->_hashStateX = Self->_hashStateY

Self->_hashStateY = Self->_hashStateZ

Self->_hashStateZ = Self->_hashStateW

unsigned v = Self->_hashStateW

v = (v ^ (v >>19)) ^ (t ^ (t >>8))

Self->_hashStateW = v

value = v

}

value &= markOopDesc::hash_mask

if (value == 0) value = 0xBAD

assert (value != markOopDesc::no_hash, "invariant")

TEVENT (hashCode: GENERATE)

return value

}

该实现位于hotspot/src/share/vm/runtime/synchronizer.cpp文件下。

因此有人会说，可以直接根据hashcode值判断两个对象是否相等吗？肯定是不可以的，因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等，但是可以直接根据hashcode值判断两个对象不等，如果两个对象的hashcode值不等，则必定是两个不同的对象。如果要判断两个对象是否真正相等，必须通过equals方法。

也就是说对于两个对象，如果调用equals方法得到的结果为true，则两个对象的hashcode值必定相等；

如果equals方法得到的结果为false，则两个对象的hashcode值不一定不同；

如果两个对象的hashcode值不等，则equals方法得到的结果必定为false；

如果两个对象的hashcode值相等，则equals方法得到的结果未知。

---