HashMap
HashMap基于哈希表的Map接口实现,以key-value的形式存在.可以通过key快速的存取value.
定义
HashMap实现了Map接口,继承了AbstractMap.其中Map接口定义了键映射到值得规则,而AbstractMap类提供Map接口骨干实现,以最大限度的减少了实现此接口所需的工作.
构造函数
- HashMap();构造一个具有默认初始容量16和加载因子为0.75的空HashMap
- HashMap(int initialCapacity);构造一个具有指定初始容量和加载因子为0.75的空HashMap
- HashMap(int initialCapacity,float loadFactor);构造一个指定初始容量和指定加载因子的空HashMap
容量表示哈希表中桶的数量,初始容量是创建hash表的容量,加载因子是hash表在其容量自动增加之前可以达到多满的尺度.
加载因子越大,对空间利用更充分,查找效率会降低;如果加载因子小,对空间造成了浪费.
HashMap数据结构
如果负载因子是0.75,初始容量为16时,name允许装填元素的最大是16*0.75=12,这个数被称为阈值,就是map中定义的threshold,超过这个阈值时,就会自动扩容.
判断key是否为null,如果为null则调用putForNullKey方法.
若不为空先计算key的hash值,根据hash值搜索在table数组中的索引位置,如果table数组在该位置有元素,通过比较是否存在key相同,如果存在则覆盖,否则将元素保存在链头.
HashMap扩容
HashMap扩容非常耗时,如果知道元素个数,就预设HashMap的容量,可以提高效率.
红黑树(1.8)
jdk1.8在链表长超过8时会转换为红黑树
HashTable
HashTable基于Dictionary类
HashMap可以key value都为null,HashTable不可以.
HashTable和HashMap的区别
HashMap线程不安全,HashTable线程安全.
HashMap内部没有实现任何线程同步相关的代码,所以性能会好一点,如果在多线程使用HashMap需要自己管理线程同步.
HashTable大部分对外接口都使用synchronized修饰,所以线程安全,但性能会差一点.
HashTable的初始容量为11,HashMap的初始容量为16
HashMap的初始容量必须是2的次幂,如果指定初始不是2的次幂,会自动转化为2的次幂.
HashMap使用自己计算Hash的方法(会依赖key的hashCode),HashTable使用key的hashCode方法.
HashTable的迭代器是enumerator迭代器,HashMap是Iterator迭代器.