先来认识一下两个常用Map
- HashMap
- HashTable
HashMap:
Map接口的一种实现，以键值对的形式存储，允许使用null作为key和value,这个类无法保证映射顺序，在扩容后，键值对的位置可能也会改变。HashMap实例的性能受hash桶的数量和加载因子的影响。hash数组默认大小是16，而且一定是2的指数。在使用hash值时，重写进行了计算。HashMap内部使用了Iterator，支持fast-fail。
HashTable:
HashTable继承自Dictionary类，所用方法都是同步的，相比HashMap，这个类的所有方法都加上了synchronized来保证同步。而且不允许key和value为空。hash数组初始化大小是11，增加的方式是size*2+1。在使用hash值时，直接使用了对象的hashCode。而由于之前版本的原因，HashTable还使用了Enumeration的方式。使用Enumeration不支持fast-fail。
HashMap的实现原理：
HashMap的底层采用数组+链表的方式来存储
数组：使用前必须事先定义长度，长度不能动态增减。经常造成容量不够或者容量有剩的情况。具有随机访问的特点，查询时利用下标定位，时间复杂度为O(1),插入和删除元素时需要移动一大片元素，时间复杂度为O(n)，特点：查询容易，插入、删除困难。
链表：占用的实际空间不是连续的，查询需要从第一个元素往后遍历，复杂度为O(n),增加和删除时只需要改变链表指针指向，时间复杂度为O(1)。
哈希表：为了满足查询、插入删除都方便的数据结构，哈希表有多种不同的实现方式，最常用的一种就是--拉链法，也就是数组+链表
hashMap内存结构图.png
可以看出，hash表由数组+链表组成，首先是一个长度为16的数组，每个数组又存储了一个链表的头结点。当有一个entrie要放入hash表中时，需要先进行hash(key)%len计算，也就是经过两次hash计算后还要进行长度取模。例如：12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。在HashMap中有一个静态内部类Entry,其中重要的属性有key、value、next,所以，enrty就是HashMap存储键值对的一个容器。所以hash表中的数组也可以说是entry数组。
HashMap的存取实现
1、put
Entry类的一个实现类是Node,Node类中有一个next属性，作用是指向下一个Node，这样的链式存储结构就是哈希表中的链表。如果两个Node中hash(key)%len得到的值相同，那么next属性就起作用了，例如 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Node[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，B.next = A,Node[0] = B,如果又进来C,index也等于0,那么C.next = B,Node[0] = C；
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
同时，HashMap也有一些优化方面的实现，但哈希表的链表越来越长时数组会进行自动扩容，扩容的时机取决于容量与加载因子的关系，加载因子默认为0.75，当扩容后hash值也会重新计算。
2、get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
从getNode方法可以看出，先定位Node数组tab中的元素，然后再通过do-while循环从链表的首节点一次往下遍历
3、key为null值时默认hash值为0，存取总是放在数组的第一个元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4、确定hash数组的索引值使用 (n - 1) & hash的方法，也就是按位取并，相当于取模mod或者取余%。 也就是数组下标相同，并不表示hashCode相同。
put：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
get：
first = tab[(n - 1) & hash]) != null
5、HashMap的初始化大小
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
6、当哈希表的容量超过默认容量时，必须调整数组的大小，当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，每次调整数组大小都需要重新散列计算索引，然后重新映射
static final int MAXIMUM_CAPACITY = 1 << 30;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
}
Java中的几种Map以及它们之间的区别？
- HashMap
非线程安全的Map - HashTable
线程安全的Map - LinkedHashMap
HashMap的一个子类，它保留了插入的顺序 - ConcurrentHashMap
线程安全的Map,在锁的粒度上比HashTable更细，性能会更好一些
Java中遍历Map的几种方式？
方式一：键和值都需要
在增强for循环中使用entries来遍历，这是最常见的并且在大多数情况下最可取的遍历方式
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
System.out.println("Key = " + entry.getKey() + ",Value = "+entry.getValue());
}
注意:增强for循环在java5中被引入所以方式一只能应用于java5或是更高的版本。如果你遍历的是一个空的map对象，增强for循环将抛出NullPointException,因此在遍历前必须检查Map对象是否是空引用
方式二：只需要键或值
在增强for循环中遍历keys或values
如果只需要map中的键或值，可以通过keySet或values来实现遍历，而不是用entrySet
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
//遍历map中的键
for(Integer key : map.keySet()){
System.out.println("Key = " + key);
}
//遍历map中的值
for(Integer value : map.values()){
System.out.println("Value = " + value);
}
注意:这个方法比entrySet遍历在性能上快了10%代码看起来也比较简洁
方式三：键和值都需要
使用Iterator遍历
如果只需要map中的键或值，可以通过keySet或values来实现遍历，而不是用entrySet
使用泛型：
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
Iterator<Map.Entry<Integer,Integer>> entries = map.entrySet().iterator();
while(entries.hasNext()) {
Map.Entry<Integer,Integer> entry = entries.next();
System.out.println("Key = "+entry.getKey() +",Value = "+entry.getValue());
}
不使用泛型：
Map map = new HashMap();
Iterator entries = map.entrySet().iterator();
while(entries.hasNext()) {
Map.Entry entry = (Map.Entry)entries.next();
Integer key = (Integer)entry.getKey();
Integer value = (Integer)entry.getValue();
System.out.println("Key = "+key +",Value = "+value);
}
注意:在keySet和vlues上也可以应用相同的方法
这种方式看起来冗余但有其优点。它是老版本java中唯一的遍历方式，另外可以再遍历时调用iterator.remove()删除entries,另外两个方法则不能。
从性能方面，该方法和增强for遍历的性能类似(方式一)
方式四：键和值都需要(通过键找值)
从键找值是一个耗时操作，与方法一相比，在不同的Map实现中该方法慢了20%-200%
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(Integer key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key = "+key+", Value = "+value);
}
所以，如果仅需要键或值可以使用方式二。如果使用的语言版本低于jdk5，或者打算遍历时删除entries，可以必须使用方式三。如果键值都需要可以使用方式一。
HashMap 和 ConcurrentHashMap 的区别？
HashMap和ConcurrentHashMap 的实现都是数组加链表，java8之后链表大小到了一定程度会变成红黑树以提升查询效率
ConcurrentHashMap对hash数组进行了分段，并且每一段都用锁保护，可以达到线程安全，而且多个线程可以同时并发的操作多个段的数据，而HashMap是非线程安全的，而且也没有分段机制。
HashTable和ConcurrentHashMap之间有什么区别？
HashTable和ConcurrentHashMap都是线程安全的Map
HashTable通过使用synchronized加锁保证线程安全，锁的力度比ConcurrentHashMap大很多，在进行同步操作的时候会将整个结构锁住。
ConcurrentHashMap使用分段锁来保证线程安全，ConcurrentHashMap默认情况下将hash数组分为16片，在加锁的时候，针对每个独立的分片进行加锁，其他分片不受影响，锁的力度相比HashTable更细。
它们都可以用于多线程的环境，但是当HashTable的大小增加到一定数量的时候，性能下降，因为在循环的时候整个方法要被长时间锁住。
因为ConcurrentHashMap引入了分片，所以不论扩容后变得多大，仅仅需要锁住hash数组中的某一部分，其它线程不需要等到遍历完成后才能访问map。
hashCode()和equals()方法的作用，二者有什么关系？
hashCode和equals都是Object类中的两个重要方法，它们的约定关系：
1、如果两个对象相等，那么他们一定有相同的哈希值（hash code）。
2、如果两个对象的哈希值相等，那么这两个对象有可能相等也有可能不相等。（需要再通过equals来判断）
Map的工作原理：Map的结构是hash数组加链表,Map是通过key的hashCode得到一个hash值，如果是HashMap，还要进进行一次hash函数运算才能得到一个hash数组索引，得到索引后，再通过equals方法对索引下这个链表的每个entry进行比较。如果有多个对象有相同的哈希值，那么它们可以放入一个hash索引对应的桶里，如果又不同的hash值，需要放入不同的桶，同一个桶里的各个对象比较就要依靠equals方法了。
所以，在判断两个对象是否相同的时候不是只依靠equals来判断，还要考虑hash值是否相同，所以equals和hashCode在对象作为key时是都必须重写的。
HashMap和HashSet
HashSet底层使用HashMap实现
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
在使用HashSet的add方法时，就是向HashMap中添加了一个键值对，key是HashSet中add的那个对象，value是一个常量。
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
HashMap和TreeMap的区别是什么？
HashMap和TreeMap都是非线程安全的。在涉及多线程的开发场景，两者都需要开发者自己通过加锁方式避免并发访问。
HashMap和TreeMap最大的区别是TreeMap具有排序功能。默认情况下，存入TreeMap中的key、value会按照key进行升序排列（可以自定义比较器传入构造函数进行自定义排序）。
在java8之前，HashMap底层是通过hash表实现的，在java8之后引入了红黑树，在一定的条件下，索引桶对应的不再是链表而是红黑树。
ConcurrentHashMap和LinkedHashMap
线程安全：
ConcurrentHashMap是线程安全的，基于分段锁，默认情况下Map会被分隔成16部分，并且可以由不同的锁锁住。LinkedHashMap是非线程安全的。
性能：
ConcurrentHashMap原本只能由一个线程进入变成可以由16个写线程（读线程几乎不受控制）同时进入，性能提升明显，但由于写操作只锁住部分，所以在遍历查询时返回的结果可能不是整个Map最新的结果。
安全性：
ConcurrentHashMap：安全性较弱，因为可以同时读写，当一个线程put未完成时，另一个线程get到值为null,这样会造成一个线程的put值被另一个线程的put值覆盖，相比HastTable(锁住整个表)、synchronzied Map（通过mutex进行加锁）的安全性较弱。
LinkedHashMap：非线程安全，安全性较差。
是否允许为空：
ConcurrentHashMap：键和值都不允许为空
LinkedHashMap：键和值允许为空
是否允许重复数据：
ConcurrentHashMap：key是唯一的，value值可以重复
LinkedHashMap：key重复会被覆盖，value值可以重复
是否有序：
ConcurrentHashMap：无序
LinkedHashMap：有序，按照put时的顺序进行遍历
应用场景：
ConcurrentHashMap：高并发，但是查询遍历一次不能保证所有数据有效性，因为只是锁住了部分内容，当有Put等写操作时不能保证最新结果，但对于高并发下的访问提升了效率。
什么样的类Map的key
在语法上任何类都可以作为Map的key值，没有任何限制，但是一般在使用自定义的类作为HashMap的key时需要注意：
1、如果重写了equals方法，必须重写hashcode方法。
2、用户自定义的key类最好使用不可变类型。这样，hashcode不可改变，可以被缓存起来，性能上更好。不可变类（如String）保证了hashCode和equals方法的结果在以后都不会发生变化。
ConcurrentSkipListMap和ConcurrentHashMap？
ConcurrentSkipListMap：是一个内部使用的跳表，是一个支持排序和并发，是线程安全的，是一个比较少用的类。
跳表：跳表是一种允许在一个有顺序的序列中进行快速查询的数据结构。
普通的链表在查询一个元素的时候，需要从链表头部开始一个一个节点进行遍历，然后找到节点。
跳表可以解决这种查询时间过长的问题，是一种以空间换时间的来提高查询效率的链表。
1.png
ConcurrentSkipListMap和ConcurrentHashMap的主要区别：
1、底层的实现不同，ConcurrentSkipListMap底层基于跳表（数据结构）。ConcurrentHashMap底层基于Hash数组和链表（一定条件后链表转为红黑树）
2、ConcurrentHashMap不支持排序，ConcurrentSkipListMap支持排序。
网友评论