WHCSRL 技术网

每个平凡人心中都有一个不平凡的世界,让Map和Set带你跨过山和大海,也穿过人山人海


HashMap和HashSet数据类型 增删改查 的时间复杂度都是 O(1)

Map

概述

在这里插入图片描述

  • Map是一个接口,如果要实例化一个对象,只能实例化其实现类HashMap或TreeMap
  • 由图可知,Map接口没有继承Iterable接口,所以Map实例的对象不能使用迭代器来打印(Map中也没有iterator()方法)
  • Map属于Key-Value类型 key值是唯一的,不能重复,但是value 是可重复的

常用方法

HashMap常用方法解释
V get(Object key)返回value对应的key;key不存在,返回null
V getOrDefault(Object key , V defaultValue)返回value对应的key;key不存在,返回defaultValue
V put(K key, V value)设置key-value;如果原来有相同的key,value更新;key和value都可以是null
V remove(Object key)删除key-value;key存在,返回value;key不存在,返回null
Collection< V > values()返回value的不重复集合
Set< K > keySet()返回所有key值的Set集合
Set< Map.Entry< K , V> > entrySet()返回所有key-value(集合中key-value是一个整体,类型是Map.Entry )的Set集合
Boolean containsKey(Object key)判断是否包含key
Boolean containsValue(Object value)判断是否包含value

在这里插入图片描述

Map.Entry< K,V >的方法
K getKey()返回 entry中的key
V getValue()返回entry中的value
V setValue(V value)替换value

底层结构

Map的底层结构HashMapTreeMap
增删改查时间复杂度通过哈希函数计算得到哈希地址 O(1)需要进行元素(key)的比较 O(log2N)
底层结构哈希表(数组+链表+红黑树)红黑树
元素是否有序无序关于key有序(通过key的大小比较)
比较和重写自定义类型要重写equals和hashcode方法key要能够进行比较,否则会抛出异常(如:put(null , value) 或 remove(null)…)
应用场景对时间复杂度要求高key需要有序

因为TreeMap是按照key进行组织的,所以查找key的时间复杂度为O(log2N),但是如果单纯的查找value的话,需要遍历所有元素,时间复杂度O(N)

观察有序性

        Map<Integer,String> treeMap = new TreeMap<>();
        treeMap.put(1,"孙少安");
        treeMap.put(12,"孙少平");
        treeMap.put(6,"孙兰花");
        treeMap.put(52,"贺秀莲");
        System.out.println(treeMap);

        Map<Integer,String> hashMap = new HashMap<>();
        hashMap.put(1,"孙少安");
        hashMap.put(12,"孙少平");
        hashMap.put(6,"孙兰花");
        hashMap.put(52,"贺秀莲");
        System.out.println(hashMap);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

在这里插入图片描述

应用

Map主要用于求数据的频率(出现次数)
某数组中有100,000个数据,求每个数据出现的次数

    public static Map<Integer,Integer> findTimes(int[] array){
        Map<Integer,Integer> map = new HashMap();
        for (int count : array) {
            if(map.get(count) == null){
                map.put(count,1);
            }else{
                int value = map.get(count);
                map.put(count,value+1);
            }
            //map.put(count,map.getOrDefault(count,0)+1);
        }
        return map;
//        重复的数据出现的此数
//        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//            if(entry.getValue() > 1){
//                System.out.println("数据" + entry.getKey() + "出现的次数" + entry.getValue());
//            }
//        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
    public static void main(String[] args) {
        int[] array = new int[100000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(1000);
        }
        System.out.println(findTimes(array));
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

Set

概述

  • Set是key类型,Set中的key值要求唯一
  • Set是个接口,实例化一个对象要用HashSet或TreeSet类进行实例化
  • Set继承了Collection类,能通过Iterator打印Set中的元素
        Set<Integer> set = new HashSet<>();
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
  • 1
  • 2
  • 3
  • 4
  • 5

常用方法

HashSet常用方法解释
boolean add(E e)插入,但是重复元素不会插入成功
boolean contains(Object e)判断是否在集合中
boolean remove(Object e)删除元素
Object[ ] toArray()set中的元素转为数组返回
boolean addAll(Collection<? extend E> c )集合c中的元素添加到set中
boolean containsAll(Collection<? extend E> c)判断集合c中的元素是否在set中
void clear()清空set中的元素

底层结构

Set的底层结构HashSetTreeSet
增删改查时间复杂度通过哈希函数计算得到哈希地址 O(1)需要进行元素(key)的比较 O(log2N)
底层结构哈希表(数组+链表+红黑树)红黑树
元素是否有序无序有序
比较和重写自定义类型要重写equals和hashCode方法key要能够进行比较,否则会抛出异常(如:add(null)或 remove(null)…)
应用场景对时间复杂度要求高key需要有序

作用

Set常用于去重

哈希表

顺序结构及平衡树中,关键码和存储位置之间没有对应的关系,查找一个元素时,要经过一系列的比较;顺序查找时间复杂度为O(N),平衡二叉树中为O(log2N)
能否不经过比较,一次性的从表中得到想要的元素?
建立一种结构,通过哈希函数将元素的存储位置与元素(关键码)之间建立一一对应的映射关系[ 存储位置=F(元素) ],查找的时间复杂度为O(1),这种结构就叫做哈希表
在这里插入图片描述

哈希冲突

不同的关键码通过相同的哈希函数计算出相同的哈希地址,叫做哈希冲突或哈希碰撞
哈希冲突是必然存在的,不能从根本上解决
如上图:14%%10 =4 24%%10=4 34%%10=4

避免哈希冲突

  1. 设计合适的哈希函数
    哈希函数的定义域包括需要存储的所有关键码,值域是0~m-1(哈希表有m个地址)
    直接定制法:线性函数 Hash(key) = A*key+B
    除数残留法:Hash(key) = key%%p(p<=m)
    2.调节负载因子
    哈希表的负载因子 = 填入的元素个数 / 哈希表的长度
    0~1范围内,负载因子越大,冲突率越高
    由于填入的关键码个数无法更改,通过调整哈希表中数组的大小来实现对负载因子的调节

解决哈希冲突

  1. 闭散列
    (1)线性探索
    从冲突位置开始,依次向后探测,直到找到下一个空位置为止,遍历完哈希表后,再从头开始
    缺点:冲突的元素会挤在一起的,而且不能随便物理删除哈希表中已有的元素
    在这里插入图片描述
    (2)二次探索
    二次探索在线性探索的基础上修改了 找下一个空位置的方法
    Hi = (H0 + i^2 )%%m
    Hi = (H0 - i^2 )%%m
    H0是计算的得到的哈希地址
    Hi 是插入的哈希地址
  2. 开散列(哈希桶)
    具有相同哈希地址的关键码通过一个单链表连接起来,各链表的头节点存储在哈希表中(哈希数组中是一个单链表头节点的引用
    当数组长度超过64并且链表长度超过8,链表变成红黑树
    在这里插入图片描述

jdk1.8采用尾插法,jdk1.7以前采用头插法
负载因子在,链表不会很长,找数据遍历单链表

有没有打NBA2k的老铁?加个好友切磋切磋哦

推荐阅读