本文共 2079 字,大约阅读时间需要 6 分钟。
java为数据结构中的映射定义了一个接口java,util.Map;它有四个实现类分别是:HashMap;Hashtable; LinkedHashMap;还有TreeMap.
Map主要是存储键值对,根据键来获取值,键不允许重复(重复会进行覆盖),值允许重复。HashMap是最常用的一个Map,它根据Hashcode的值来存储数据,根据键可以直接获取它的值,具有很高的访问速度,遍历的时候都是随机的,不能保证以存储时候的顺序取出。
HashMap不支持线程的同步,在多线程环境下去使用它,会有数据的不一致问题,如果需要同步,可以用Collections.synchronizedMap()方法来是HashMap具有同步的能力,或者使用ConcurrentHashMap。Hashtable与HashMap类似,它继承自Dictionary类,不同的是:它不允许记录的键或者值为空;它支持线程的同步,也就是说是线程安全的,即任一时刻只有一个线程能写Hashtable,因此也导致了 Hashtable在写入时会比较慢。
LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,使用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时用带参数,按照应用次数排序。在遍历的时候会比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比 LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关。
TreeMap是先SortMap接口,能够把保存的数据根据键排序,默认的是按键值的升序排序。
一般情况下,我们用的最多的是HashMap,在Map 中插入、删除和定位元素,HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键,那么TreeMap会更好。如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列.
HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry实际上是一个单向的链表结构,具有Next指针,可以连接下一个Entry实体。(JDK1.8中长度大于8时,链表会转为红黑树)
为什么用数组和链表呢? 其实数组在这里是确定桶的位置,利用元素的Key的hash值对数组的长度取模得到,链表是用来解决hash冲突问题,当出现hash值一样的情形,就在数组上的对应为位置形成一条链表。
hashmap中put元素的过程是什么样么?
对key的hashCode()做hash运算,计算index; 如果没碰撞直接放到bucket里; 如果碰撞了,以链表的形式存在buckets后; 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树(JDK1.8中的改动); 如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity),就要resize。hashmap中get元素的过程是什么样么?
对key的hashCode()做hash运算,计算index; 如果在bucket里的第一个节点里直接命中,则直接返回; 如果有冲突,则通过key.equals(k)去查找对应的Entry;若为树,则在树中通过key.equals(k)查找,O(logn);
若为链表,则在链表中通过key.equals(k)查找,O(n)。
HashMap在并发编程环境下有什么问题啊?
(1)多线程扩容,引起的死循环问题
(2)多线程put的时候可能导致元素丢失
(3)put非null元素后get出来的却是null
**在jdk1.8中,死循环问题已经解决。其他两个问题还是存在。
解决:
比如 ConcurrentHashmap,Hashtable等线程安全等集合类。
一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当HashMap当key,而且String最为常用。
(1)因为字符串是不可变的,所以在它创建的时候hashcode就被缓存了,不需要重新计算。这就使得字符串很适合作为Map中的键,字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
(2)因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法
是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。1 两个对象相等,hashcode一定相等 2 两个对象不等,hashcode不一定不等 3 hashcode相等,两个对象不一定相等 4 hashcode不等,两个对象一定不等
转载地址:http://dyxen.baihongyu.com/