Java Map 与 Set 数据结构及实现原理

Map 和 Set

Map 和 Set 用于搜索
搜索树：二叉搜索树 -> AVL 树 -> 红黑树
AVL 树：高度平衡的二叉搜索树
TreeMap 和 TreeSet 底层是红黑树，每次存储元素都得进行大小比较

二叉搜索树

二叉搜索树：如果左子树不为空，那么左子树所有节点都小于根节点；如果右子树不为空，那么右子树所有节点都大于根节点；它的左右子树都是二叉搜索树。
二叉搜索树的中序遍历是有序的

查找

比 key 大往右找，比 key 小往左找。

// 查找
public boolean search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val > key) {
            cur = cur.left;
        } else if (cur.val < key) {
            cur = cur.right;
        } else {
            return true;
        }
    }
    return false;
}

分析

时间复杂度：
- 最好情况：O(logN)，完全二叉树
- 最坏情况：O(N)，单分支的二叉树

插入

// 插入
public boolean insert(int key) {
    TreeNode node = new TreeNode(key);
    TreeNode parent = null;
    if (root == null) {
        root = node;
        return true;
    }
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            parent = cur;
            cur = cur.right;
        } else if (cur.val > key) {
            parent = cur;
            cur = cur.left;
        } else {
            // 在二叉搜索树中不能有相同的数字，比如 5，有一个 5 就可以了
            return false;
        }
    }
    if (parent.val < key) {
        parent.right = node;
    } else {
        parent.left = node;
    }
    return true;
}

删除

第一种情况：cur.left == null 要删除的节点是 cur。cur 可能是根节点，也可能是某个节点的左边或右边。

示意图

第二种情况：cur.right == null 要删除的节点是 cur。cur 可能是根节点，也可能是某个节点的左边或右边。

示意图

第三种情况：cur.left != null && cur.right != null 使用替换法进行删除。替换为左树中最大的值，或者是右树中最小的值。替换完之后删除这个去替换的值。

示意图

// 删除
private void removeNode(TreeNode cur, TreeNode parent) {
    if (cur.left == null) {
        // 要删除的是根节点
        if (cur == root) {
            root = cur.right;
        } else if (cur == parent.left) {
            parent.left = cur.right;
        } else {
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        if (cur == root) {
            root = cur.left;
        } else if (cur == parent.left) {
            parent.left = cur.left;
        } else {
            parent.right = cur.left;
        }
    } else {
        // cur.left != null && cur.right != null
        TreeNode parentTarget = cur;
        TreeNode target = cur.right;
        // 在右树中找最小值
        while (target.left != null) {
            parentTarget = target;
            target = target.left;
        }
        // 直到找到右树中的最左边的树 cur.val = target.val
        cur.val = target.val;
        // 删除 target
        if (parentTarget.left == target) {
            parentTarget.left = target.right;
        } else {
            // parentTarget.right == target
            parentTarget.right = target.right;
        }
    }
}

Map

Map 是一种 (k, v) 结构的数据结构。
Map 可以进行去重。TreeMap 不可以插入 null 的 key，HashMap 可以插入 null 的 key，因为红黑树是要进行比较的，哈希表是不进行比较的。

Map<String, Integer> map = new TreeMap<>(); // 底层是红黑树，查找的时间复杂度 O(N*logN)
Map<String, Integer> map1 = new HashMap<>(); // 底层是哈希表，查找的时间复杂度 O(1)
// 哈希表 = 数组 + 链表 + 红黑树

Map 的使用

示意图

public static void main(String[] args) {
    Map<String, Integer> map = new TreeMap<>(); // 底层是红黑树，查找的时间复杂度 O(N*logN)
    // 插入元素 map.put("push", 3); // push 出现了 3 次
    // 获取元素，给定一个 key 值可以获取它的 value 值
    Integer val = map.get("push");
    Integer val1 = map.get("aaa"); // null
    // 获取 val 值，如果没有这个值，返回一个默认值
    Integer val2 = map.getOrDefault("bbb", 99999);
    System.out.println(val);
    // 删除 key 值
    // map.remove("push");
    // 把所有的 key 放入一个集合中
    Set<String> set = map.keySet();
    System.out.println(set);
    // 获取 values 中的所有值
    ArrayList<Integer> value = new ArrayList<>(map.values());
    System.out.println(value);
    // 把 Map.Entry<String,Integer>当做 Set 中的一个节点
    // map.entrySet() 用于获取这种节点
    Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
    for (Map.Entry<String, Integer> entry : entrySet) {
        System.out.println("key: " + entry.getKey() + " value: " + entry.getValue());
    }
    // boolean map.containsKey("push"); 判断是否含有 key
    // boolean map.containsValue(3); 判断是否含有 value
    Map<String, Integer> map1 = new HashMap<>(); // 底层是哈希表，查找的时间复杂度 O(1)
    // 哈希表 = 数组 + 链表 + 红黑树
}

Set

Set 是一种只有 key 的模型。

Set 的使用

Set 是要进行去重的。
TreeSet 不可以插入 null 的 key，HashSet 可以插入 null 的 key，因为红黑树是要进行比较的，哈希表是不进行比较的。

public static void main(String[] args) {
    Set<String> set = new TreeSet<>();
    set.add("push");
    set.add("hello");
    set.add("world");
    // set 是无序的
    System.out.println(set);
    Iterator<String> it = set.iterator();
    while (it.hasNext()) {
        System.out.println(it.next());
    }
}

哈希表

查找可以一次定位到该元素，时间复杂度为 O(1)。

哈希冲突 (碰撞)：不同的 key 通过相同的哈希函数得到相同的值。哈希冲突是必然产生的，我们要做的是降低冲突的概率。

示意图

解决哈希冲突：哈希函数的设计要合理。哈希函数要简单。哈希表中要均匀分到数组中去。哈希表的范围要合理，比如有 m 个地址，存储位置就是 [0, m-1]。

示意图

负载因子的调节（重点）

负载因子影响了哈希冲突，负载因子越大冲突率越高。
哈希表中的负载因子定义为：a = 填入表中的元素个数 / 哈希表的长度。比如：a = 8 / 10 = 0.8。

如果降低冲突率就要降低负载因子，因此要扩容哈希表的大小。不增加插入的元素是不现实的，给定一个阈值，如果超过了就扩大哈希表的容量。

示意图

闭散列

开放定址法，如果没有达到阈值，但是冲突了，就放到冲突的下一个空的位置上，这个也叫线性探测。
线性探测的缺点：把冲突的元素都集中放到了一起。
二次探测：为了解决线性探测的缺点，通过公式进行处理，H0 是当前冲突的位置，i 是出现冲突的次数，m 是哈希表的大小，Hi 表示冲突后，下一次要放的位置。

示意图

线性探测对于空间的利用率不高。

开散列

开散列：又叫链地址法，为了解决空间利用率不高的问题，开散列是数组 + 链表 + 红黑树的模式。
把冲突的元素挂到同一个空间下的链表上。
Java 是采用开散列的方式实现的。

示意图

扩容之后需要重新哈希，因为数组长度变了，要重新计算节点存放的位置。
遍历哈希数组中每个数组元素，都要重新计算节点位置。

示意图

package Demo1;
import java.util.Arrays;

public class HashBuck {
    // 链表数组，数组中的每一个元素都时链表的头结点
    public class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node[] array;
    public int usedSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBuck() {
        array = new Node[10];
    }

    public void put(int key, int value) {
        int index = key % array.length;
        // 遍历 index 下标的链表 是否存在 key 存在就更新 value 不存在就头插这个节点
        Node node = new Node(key, value);
        // 该链表的头结点
           array[index];
         (cur != ) {
             (cur.key == key) {
                
                cur.val = value;
                ;
            }
            cur = cur.next;
        }
        
        node.next = array[index];
        array[index] = node;
        usedSize++;
        
         (doLoadFactor() > DEFAULT_LOAD_FACTOR) {
            
            
            resize();
        }
    }

       {
        
        Node[] newArray =  [ * array.length];
         (   ; i < array.length; i++) {
               array[i];
             (cur != ) {
                   cur.next;
                
                   cur.key % newArray.length;
                
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = tmp;
            }
        }
        array = newArray;
    }

    
       {
         usedSize *  / array.length;
    }

    
       {
           key % array.length;
           array[index];
         (cur != ) {
             (cur.key == key) {
                
                 cur.val;
            }
            cur = cur.next;
        }
         -;
    }
}

HashMap 是线程不安全的，因为采用了头插法，后面采用了尾插法变得安全了，ConcurrentHashMap 是线程安全的，之后学到了线程就可以理解了。
如果 key 是 String，Person 类型就不能除以数组的长度了，该怎么找到对应的下标呢？可以用 hashcode 来将自定义类型转化为整形类型。

hashCode 和 equals

示意图

HashMap 和 HashSet

public static void main(String[] args) {
    HashMap<String, Integer> hashMap = new HashMap<>();
    hashMap.put("hello", 2);
    hashMap.put("abcde", 10);
    hashMap.put("abc", 11);
    Integer val = hashMap.get("hello");
    System.out.println(val);
    // 遍历 map
    System.out.println(hashMap);
    for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
        System.out.println("key:" + entry.getKey() + " value:" + entry.getValue());
    }
    // Map 不支持迭代器遍历，Set 支持迭代器遍历
    // 可以将 Map 转化为 Set 进行迭代器遍历
    HashMap<Student, Integer> hashMap1 = new HashMap<>();
    hashMap1.put(new Student(), 2);
    hashMap1.put(new Student(), 2);
    hashMap1.put(null, 2);
    // TreeMap<Student, Integer> hashMap2 = new TreeMap<>();
    // hashMap2.put(new Student(), 3);
    // hashMap2.put(new Student(), 3);
    // Sutdent 不能进行比较
    // set 可以去重，Set 的底层是 HashMap
    // 每次存储元素的时候，默认的 value 都是一个 Object 对象
    HashSet<String> set = new HashSet<>();
    set.add("hello");
    set.add("world");
    set.add("hello");
    System.out.println(set);
}

面试题

只出现一次的数字宝石与石头旧键盘随机链表的复制

示意图

统计 6 个数中数字出现的次数

public static void main(String[] args) {
    int[] array = {1, 1, 2, 2, 3, 3};
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        if (!map.containsKey(array[i])) {
            map.put(array[i], 1);
        } else {
            int k = map.get(array[i]);
            k++;
            map.put(array[i], k);
        }
    }
    System.out.println(map);
}

前 k 个高频单词

示意图

如果频率相同放入堆中要使用大根堆，要让 love 排在 i 的前面

示意图

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 1. 统计单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (!map.containsKey(s)) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        // 2. 把单词和出现的次数当做一个整体放入小根堆中
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                // 放元素的时候，如果频率相同，我们转变为大根堆 -> 按照单词的字典序进行排序
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                // 没有放满小根堆 minHeap.add(entry);
                minHeap.offer(entry);
            } else {
                // 放满了和堆顶元素比较大小
                // 如果比堆顶元素还大，就入堆
                int v = minHeap.peek().getValue();
                 (v < entry.getValue()) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }  {
                    
                     (v == entry.getValue()) {
                         (minHeap.peek().getKey().compareTo(entry.getKey()) > ) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        
        List<String> arr =  <>();
         (   ; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            arr.add(top.getKey());
        }
        
        Collections.reverse(arr);
         arr;
    }
}

HashMap 的源码

如果达到一定条件会把哈希表编程红黑树：如果链表的长度大于 8 并且数组的长度大于 64 就会进行树化。

示意图

Java Map 与 Set 数据结构及实现原理

Map 和 Set

二叉搜索树

查找

分析

插入

删除

Map

Map 的使用

Set

Set 的使用

哈希表

负载因子的调节（重点）

闭散列

开散列

HashMap 和 HashSet

面试题

HashMap 的源码

更多推荐文章

相关免费在线工具

Java Map 与 Set 数据结构及实现原理

Map 和 Set

二叉搜索树

查找

分析

插入

删除

Map

Map 的使用

Set

Set 的使用

哈希表

负载因子的调节（重点）

闭散列

开散列

HashMap 和 HashSet

面试题

HashMap 的源码

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具