• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

集合框架-HashMap&HashSet&LinkedHshMap

开发技术 开发技术 5天前 17次浏览

一、HashMap的底层实现

HashMap底层是基于数组和链表实现的。其中最重要的参数:容量和负载因子。

容量的默认大小事16,负载因子是0.75,当HashMap的size>16*0.75的时候就会发生库容(容量和负载因子都可以自由调整)

Hashmap实现了Map接口,允许放入null元素,出了该类未实现同步外,其余和HashTable大致相同,跟TreeMap不同,该容器不保证冤死顺序,根据需要该容器可能对元素重新哈希,元素的顺序也会被重新打散,因此不同时间迭代同一个HashMap的顺序可能会不同。

二、HashMap的put(key,value)方法

首先会将传入的可以、做hash运算计算出hashCode,然后根据数组长度取模计算出在数组中的index下表

由于在计算机中位运算比取模运算效率高,所以HashMsap规定数组的长度为2n。这样用2n-1做位运算与取模效果一致,并且效率要高出许多

由于数组的长度有限,所以难免出现不同放入key通过运算得到的index相同,这种情况可以利用链表来解决,HashMap会在table[index]出形成链表,采用头插法将数据插入链表中

三、HashMap的get(key)fangfa

get和put类似,也是讲传入的可以计算出index,如果该位置上是一个链表就需要比那里整个链表,通过key.equals(k)来找到对应的元素。

遍历方式:

第一种

Iterator<Map.Entry<String, Integer>> entryIterator=map.entrySet().iterator();
        while(entryIterator.hasNext()){
            Map.Entry<String,Integer> next=entryIterator.next();
            System.err.println("key="+next.getKey()+"value="+next.getValue());
        }

第二种

Iterator iterator=map.keySet().iterator();
        while(iterator.hasNext()){
            String key=iterator.next();
            System.err.println("key="+key+"value="+map.get(key));
        }

第三种

map.forEach((key,value)->{
            System.err.println("key="+key+"value="+value);
        });

第一种可以把key value同时取出,第二种还得需要通过key去一次value,效率较低,第三种需要JDK1.8以上,通过外层遍历table,内层遍历链表或红黑树。

四、为什么多线程场景下不推荐使用HashMap

并发环境下使用HashMap容易出现死循环。并发场景下发生扩容,调用resize()方法里的rehash()时,容易出现环形链表。这样当获取一个不存在的key时,计算出的index正好是环形链表的下标时就会出现死循环

所以,HashMap只能在单线程中使用,并且尽量的预设容量,尽可能的减少扩容发

在JDK1.8中对HashMap进行了优化:当hash碰撞之后写入链表的长度超过阈值(默认为8),链表将会转换成红黑树。假设hash冲突非常严重,一个数组后面接了很长的链表,此时查询的时间复杂度就是O(n)。如果是红黑树,时间复杂度就是O(logn)。大大提高了查询的效率。多线程场景下推荐使用ConcurrentHashMap。

五、HashSet的底层实现

HashSet是对HashMap的简单包装,对HashSet的函数调用都会转换成合适的HashMap方法,因此HashSet的实现非常简单。

成员变量

首先了解下HashSet的成员变量

  private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

发现主要有两个变量:

map:用于存放最终数据

PRESENT:是所有写入map的value值

构造函数

public HashSet() {
        map = new HashMap<>();
    }

 public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

 public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

构造函数很简单,利用了HashMap初始化了map

add

 public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

比较关键的就是这个add()方法。可以看出他是将存放的对象当做了HashMap的键,value都是相同的PRESENT.由于HashMap的key是不能重复的,所以每当有重复的值写入到HashSet中只能存放不重复的元素


喜欢 (0)