Java Map和Set使用詳解(最新推薦)

更新時(shí)間：2025年09月29日 08:50:19 作者：英雄不問出處

本文介紹Java中Map和Set的實(shí)現(xiàn)結(jié)構(gòu),TreeMap/TreeSet基于紅黑樹,HashMap/HashSet基于哈希表,討論哈希沖突處理、負(fù)載因子、線程安全及hashCode/equals的作用,涵蓋二叉搜索樹特性、查找效率、插入刪除方法等關(guān)鍵內(nèi)容,感興趣的朋友一起看看吧

Map和Set

map和set用于搜索
搜索樹，二叉搜索樹 -> AVL樹 -> 紅黑樹
AVL樹：高度平衡的二叉搜索樹
TreeMap和TreeSet底層是紅黑樹，每次存儲(chǔ)元素都得進(jìn)行大小比較

二叉搜索樹

二叉搜索樹：如果左子樹不為空，那么左子樹所有節(jié)點(diǎn)都小于根節(jié)點(diǎn)，如果右子樹不為空，那么右子樹所有節(jié)點(diǎn)都大于根節(jié)點(diǎn)，它的左右子樹都是二叉搜索樹
二叉搜索樹的中序遍歷是有序的

查找

比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;
    }

分析：

時(shí)間復(fù)雜度：
最好情況：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{
                // 在二叉搜索樹中只能不能有相同的數(shù)字,比如5,有一個(gè)5就可以了,只要有這個(gè)數(shù)就可以了
                return false;
            }
        }
        if(parent.val < key){
            parent.right= node;
        }else{
            parent.left = node;
        }
        return true;
    }

刪除

第一種情況：cur.left == null
要?jiǎng)h除的節(jié)點(diǎn)是cur
cur是根節(jié)點(diǎn)
cur是某個(gè)節(jié)點(diǎn)的左邊
cur是某個(gè)節(jié)點(diǎn)的右邊

2. 第二種情況：cur.right == null
要?jiǎng)h除的節(jié)點(diǎn)是cur
cur是根節(jié)點(diǎn)
cur是某個(gè)節(jié)點(diǎn)的左邊
cur是某個(gè)節(jié)點(diǎn)的右邊

3. 第三種情況：cur.left != null && cur.right != null
使用替換法進(jìn)行刪除
替換為左樹中最大的值
或者是右樹中最小的值
替換完之后刪除這個(gè)去替換的值

// 刪除
    private void removeNode(TreeNode cur, TreeNode parent) {
        if(cur.left == null){
            // 要?jiǎng)h除的是根節(jié)點(diǎn)
            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;
            // 刪除target
            if(parentTarget.left == target) {
                parentTarget.left = target.right;
            }else{
                // parentTarget.right == target
                parentTarget.right = target.right;
            }
        }
    }

Map

map是一種(k，v)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)
map可以進(jìn)行去重，TreeMap不可以插入null的key，HashMap可以插入null的key，因?yàn)榧t黑樹是要進(jìn)行比較的，哈希表是不進(jìn)行比較的

 Map<String,Integer> map = new TreeMap<>();// 底層是紅黑樹,查找的時(shí)間復(fù)雜度O(N*logN)
 Map<String,Integer> map1 = new HashMap<>();// 底層是哈希表,查找的時(shí)間復(fù)雜度O(1)
 // 哈希表 = 數(shù)組 + 鏈表 + 紅黑樹

Map的使用

public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();// 底層是紅黑樹,查找的時(shí)間復(fù)雜度O(N*logN)
        // 插入元素
        map.put("push",3);// push出現(xiàn)了3次
        // 獲取元素,給定一個(gè)key值可以獲取它的value值
        Integer val = map.get("push");
        Integer val1 = map.get("aaa");// null
        // 獲取val值,如果沒有這個(gè)值,返回一個(gè)默認(rèn)值
        Integer val2 = map.getOrDefault("bbb",99999);
        System.out.println(val);
        // 刪除key值
        // map.remove("push");
        // 把所有的key放入一個(gè)集合中
        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>當(dāng)做Set中的一個(gè)節(jié)點(diǎn)
        // map.entrySet()用于獲取這種節(jié)點(diǎn)
        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<>();// 底層是哈希表,查找的時(shí)間復(fù)雜度O(1)
        // 哈希表 = 數(shù)組 + 鏈表 + 紅黑樹
    }

Set

set是一種只有key的模型

Set的使用

Set是要進(jìn)行去重的
TreeSet不可以插入null的key，HashSet可以插入null的key，因?yàn)榧t黑樹是要進(jìn)行比較的，哈希表是不進(jìn)行比較的

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

哈希表

查找可以一次定位到該元素，時(shí)間復(fù)雜度為O(1)

哈希沖突(碰撞)：不同的key通過相同的哈希函數(shù)得到相同的值
哈希沖突是必然產(chǎn)生的，我們要做的是降低沖突的概率

解決哈希沖突：哈希函數(shù)的設(shè)計(jì)要合理
哈希函數(shù)要簡(jiǎn)單
哈希表中要均勻分到數(shù)組中去
哈希表的范圍要合理，比如有m個(gè)地址，存儲(chǔ)位置就是[0,m-1]

負(fù)載因子的調(diào)節(jié)（重點(diǎn)）

負(fù)載因子影響了哈希沖突，負(fù)載因子越大沖突率越高
哈希表中的負(fù)載因子定義為：
a = 填入表中的元素個(gè)數(shù) / 哈希表的長(zhǎng)度
比如：a = 8 / 10 = 0.8

如果降低沖突率就要降低負(fù)載因子，因此要擴(kuò)容哈希表的大小，不增加插入的元素是不現(xiàn)實(shí)的，給定一個(gè)閾值，如果超過了就擴(kuò)大哈希表的容量

閉散列

開放定址法，如果沒有達(dá)到閾值，但是沖突了，就放到?jīng)_突的下一個(gè)空的位置上，這個(gè)也叫線性探測(cè)
線性探測(cè)的缺點(diǎn)：把沖突的元素都集中放到了一起
二次探測(cè)：為了解決線性探測(cè)的缺點(diǎn)，通過公式進(jìn)行處理，H0是當(dāng)前沖突的位置，i是出現(xiàn)沖突的次數(shù)，m是哈希表的大小，Hi表示沖突后，下一次要放的位置

4. 線性探測(cè)對(duì)于空間的利用率不高

開散列

開散列：又叫鏈地址法，為了解決空間利用率不高的問題，開散列是數(shù)組 + 鏈表 + 紅黑樹的模式
把沖突的元素掛到同一個(gè)空間下的鏈表上
Java是采用開散列的方式實(shí)現(xiàn)的

4. 擴(kuò)容之后需要重新哈希，因?yàn)閿?shù)組長(zhǎng)度變了，要重新計(jì)算節(jié)點(diǎn)存放的位置
5. 遍歷哈希數(shù)組中每個(gè)數(shù)組元素，都要重新計(jì)算節(jié)點(diǎn)位置

package Demo1;
import java.util.Arrays;
public class HashBuck {
    // 鏈表數(shù)組,數(shù)組中的每一個(gè)元素都時(shí)鏈表的頭結(jié)點(diǎn)
    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下標(biāo)的鏈表 是否存在key 存在就更新value 不存在就頭插這個(gè)節(jié)點(diǎn)
        Node node = new Node(key,value);
        // 該鏈表的頭結(jié)點(diǎn)
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                // 如果插入的這個(gè)key相同就替換這個(gè)key
                cur.val = value;
                return;
            }
            cur = cur.next;
        }
        // 沒有找到這個(gè)節(jié)點(diǎn)就頭插
        node.next = array[index];
        array[index] = node;
        usedSize++;
        // 負(fù)載因子大于閾值
        if(doLoadFactor() > DEFAULT_LOAD_FACTOR){
            // 擴(kuò)容
            // array = Arrays.copyOf(array,2*array.length);
            resize();
        }
    }
    private void resize(){
        // 建一個(gè)新的數(shù)組
        Node[] newArray = new Node[2*array.length];
        for(int i = 0;i < array.length;i++){
            Node cur = array[i];
            while(cur != null){
                Node tmp = cur.next;
                // 每次都要算新數(shù)組的下標(biāo)因?yàn)槭且粋€(gè)鏈表有很多個(gè)節(jié)點(diǎn)
                int newIndex = cur.key % newArray.length;
                // 頭插法
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = tmp;
            }
        }
        array = newArray;
    }
    // 計(jì)算負(fù)載因子
    private float doLoadFactor(){
        return usedSize * 1.0f / array.length;
    }
    // 獲取對(duì)應(yīng)key的value值
    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                // 如果插入的這個(gè)key相同就替換這個(gè)key
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}

HashMap是線程不安全的，因?yàn)椴捎昧祟^插法，后面采用了尾插法變得安全了，ConcurrentHashMap是線程安全的，之后學(xué)到了線程就可以理解了
如果key是String，Person類型就不能除以數(shù)組的長(zhǎng)度了，該怎么找到對(duì)應(yīng)的下標(biāo)呢？
可以用hashcode來將自定義類型轉(zhuǎn)化為整形類型

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轉(zhuǎn)化為Set進(jìn)行迭代器遍歷
        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不能進(jìn)行比較
        // set可以去重,Set的底層是HashMap
        // 每次存儲(chǔ)元素的時(shí)候,默認(rèn)的value都是一個(gè)Object對(duì)象
        HashSet<String> set = new HashSet<>();
        set.add("hello");
        set.add("world");
        set.add("hello");
        System.out.println(set);
    }

面試題

只出現(xiàn)一次的數(shù)字
 寶石與石頭
 舊鍵盤
 隨機(jī)鏈表的復(fù)制

統(tǒng)計(jì)6個(gè)數(shù)中數(shù)字出現(xiàn)的次數(shù)

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個(gè)高頻單詞

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

class Solution {
   public List<String> topKFrequent(String[] words, int k) {
        // 1. 統(tǒng)計(jì)單詞出現(xiàn)的次數(shù)
        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. 把單詞和出現(xiàn)的次數(shù)當(dāng)做一個(gè)整體放入小根堆中
        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){
            // 放元素的時(shí)候,如果頻率相同,我們轉(zhuǎn)變?yōu)榇蟾?-> 按照單詞的字典序進(jìn)行排序
            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);
            }else{
                // 放滿了和堆頂元素比較大小
                // 如果比堆頂元素還大,就入堆
                int v = minHeap.peek().getValue();
                if(v < entry.getValue()){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else{
                    // 出現(xiàn)頻率相同,比較字典序大小
                    if(v == entry.getValue()){
                        if(minHeap.peek().getKey().compareTo(entry.getKey()) > 0){
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        // 2 3 4 -> 4 3 2
        List<String> arr = new ArrayList<>();
        for(int i = 0;i < k;i++){
            Map.Entry<String,Integer> top = minHeap.poll();
            arr.add(top.getKey());
        }
        // 逆置
        Collections.reverse(arr);
        return arr;
    }
}