HashMap和HashTable

  • HashMap:

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

hashmap的键和值都是对象,并且不能包含重复键,但可以包含重复值。HashMap允许null key和null value,但是hashtable不允许。

HashMap是Hashtable的轻量级实现,但是HashMap不是线程安全的,由于非线程安全,效率上可能高于Hashtable。

 

hashMap工作原理:

  • 通过put()方法保存键和值时,先对key调用hashCode()方法,通过返回的hashCode用来找到bucket位置来存储Entry对象(Entry对象类似于链表的节点),而在bucket中存储的是keyvalue,作为map.Entry。
  • 当两个对象的hashCode相同时,bucket位置相同,这时就会发生碰撞,因为HashMap使用链表存储对象,所以会去找是否存在该key,如果存在则替换其value,不存在则将这个Entry存储在链表中。
  • 当用get查找时,会根据key计算hashCode找到对应bucket,然后根据key查找对应的Entry( 找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象),找到后将value返回。
  • 如果HashMap的大小超过了负载因子(load factor)定义的容量(默认的负载因子大小为0.75),也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing。
  • 当重新调整HashMap大小时,在多线程的情况下,可能产生条件竞争(race condition)。因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

HashMap源代码:

//初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

因为负载因子为0.75,16*0.75=12,所以当保存第12个元素的时候会进行rehashing,会导致输出的结果顺序有变化。

例子:

for(int i = 0;i<20;i++){
    hashMap.put(i+"", i);
}

Iterator iterator = hashMap.entrySet().iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

输出结果:

11=11
12=12
13=13
14=14
15=15
16=16
17=17
18=18
19=19
0=0
1=1
2=2
3=3
4=4
5=5
6=6
7=7
8=8
9=9
10=10

总结:Set对每个对象只接受一次,并使用自己内部的排序方法(通常,你只关心某个元素是否属于 Set,而不关心它的顺序–否则应该使用List)。Map同样对每个元素保存一份,但这是基于”键”的,Map也有内置的排序,因而不关心元素添加的 顺序。如果添加元素的顺序对你很重要,应该使用 LinkedHashSet或者LinkedHashMap.

HashMap遍历使用Demo:

HashMap<String,Integer> hashMap = new HashMap<>();
long startTime = System.currentTimeMillis();
for(int i = 0;i<TIME;i++){
    hashMap.put(i+"", i);
}
Iterator<Entry<String,Integer>> iterator = hashMap.entrySet().iterator();
while(iterator.hasNext()){
    Entry<String,Integer> entry = iterator.next();
    System.out.println("key is:"+entry.getKey());
    System.out.println("value is:"+entry.getValue());
}

 

  • HashTable:

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

HashTable的许多方法都是用synchronized修饰的。

总结:

HashMap 线程不安全 运行有null的键和值 运行速度快 实现了Map接口
HashTable 线程安全 不允许有null的键和值 占用系统资源多,速度稍慢 Dictionary是过时的了,所以在后面的版本也实现了Map接口

 

 

发表评论

邮箱地址不会被公开。 必填项已用*标注