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

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

Map

概述

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

常用方法

底层结构

因为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

常用方法

底层结构

作用

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的老铁？加个好友切磋切磋哦