devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构-Set和Map_set和map是基于什么实现的

作者：小蓝xlanll | 2024-05-15 01:04:54

赞

踩

set和map是基于什么实现的

7、集合和映射(set and map)

集合

Set

  • void add(E) 添加一个元素，不能添加重复元素
  • void remove(E) 删除元素
  • boolean contains(E) 是否包含某元素
  • int getSize() 尺寸大小
  • boolean isEmpty() 是否为空

典型应用

  • 客户统计
  • 词汇量统计

基于二分搜索树实现集合

基于链表实现集合

  • 二分搜索树和链表均属于动态数据结构

在这里插入图片描述

集合的时间复杂度分析

基于链表构成的集合

  • 增 add O(n)
  • 删 remove O(n)
  • 查 contains O(n)

基于二分搜索树构成的集合

下面h用来表示二分搜索树的高度或者层数

  • 增 add O(h) = O(logn)（平均） O(n)（最差）
  • 删 remove O(h) = O(logn)（平均）O(n)（最差）
  • 查 contains O(h) = O(logn)（平均）O(n)（最差）

对于一颗满二分搜索树，有如下情况：

在这里插入图片描述

h层总共有多少节点？

在这里插入图片描述

随着n越来越大，n与logn之间的差距越来越大，所以也可以得出logn是一个非常快的复杂度：

在这里插入图片描述

但是同样也有特殊情况，同样的数据，可以对应不同的二分搜索树。下面这种情况，同样也是二分搜索树，但是这样的二分搜索树的层数等于链表的节点数目。这种情况下，二分搜索树就退化成了链表。

在这里插入图片描述

总结这两种集合的组成结构时间复杂度：

在这里插入图片描述

集合的问题

有序集合和无序集合

  • 有序集合中的元素具有顺序性（基于二分搜索树或者平衡二叉树实现，为了顺序性降低了部分效率）
  • 无序集合中的元素没有顺序性（基于链表实现（效率低），基于哈希表实现能够更快提高效率（效率甚至高于基于二分搜索树））
  • 多重集合：集合中的元素可以重复

映射Map(字典)

在这里插入图片描述

  • 存储（键，值）数据对的数据结构（key，value）
  • 根据键（key），寻找值（value）
  • 非常容易的使用链表和二分搜索树实现

在这里插入图片描述

  • 方法实现：
    • void add(k,v)
    • v remove(k)
    • boolean contains(k)
    • v get(k)
    • void set(k,v)
    • int getSize(
    • boolean isEmpty()

基于链表的映射实现

public class LinkedListMap<K,V> implements Map<K,V> {

    private class Node{
        public K key;
        public V value;
        public Node next;

        public Node(K key,V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key) {
            this(key,null,null);
        }

        public Node() {
            this(null,null,null);
        }

        @Override
        public String toString() {
            return key.toString()+" : "+value.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        dummyHead = new Node();
        size = 0;
    }

    private Node getNode(K key) {
        Node node = dummyHead.next;
        while(node != null) {
            if(node.key.equals(key))
                return node;
            node = node.next;
        }
        return null;
    }

    //添加
    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if(node == null) {
            dummyHead.next = new Node(key,value,dummyHead.next);
            size ++;
        } else {
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        Node pre = dummyHead;
        while(pre.next != null) {
            if(pre.next.key.equals(key))
                break;
            pre = pre.next;
        }

        if(pre.next != null) {
            Node delNode = pre.next;
            pre.next = delNode.next;
            delNode.next = null;
            size --;
            return delNode.value;
        }

        return null;
    }

    @Override
    public boolean contains(K key) {
        return getNode(key)!=null;
    }

    @Override
    public V get(K key) {
        return getNode(key).value;
    }

    //修改
    @Override
    public void set(K key, V newValue) {
        Node node = getNode(key);
        if(node == null) {
            throw new IllegalArgumentException(key+"is not exist");
        } else {
            node.value = newValue;
        }
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109

基于二分搜索树的映射实现

import binaryTree.BST;

public class BSTMap<K extends Comparable<K>,V> implements Map<K,V> {

    private class Node{
        public K key;
        public V value;
        public Node left,right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap() {
        root = null;
        size = 0;
    }

    //向二分搜索树中添加（key,value）
    private Node add(Node node, K key, V value) {
        if(node == null) {
            size ++;
            return new Node(key,value);
        }

        if(key.compareTo(node.key) < 0) {
            node.left = add(node.left,key,value);
        } else if(key.compareTo(node.key) > 0) {
            node.right = add(node.right,key,value);
        } else {
            node.value = value;
        }

        return node;
    }

    @Override
    public void add(K key, V value) {
        root = add(root,key,value);
    }

    //删除任意节点的元素
    @Override
    public V remove(K key) {
        Node node = getNode(root,key);
        if(node != null) {
            root = remove(root,key);
            return node.value;
        }

        return null;
    }

    //删除掉以node为根的二分搜索树中以键为key的节点
    private Node remove(Node node, K key) {
        if(node == null) {
            return null;
        }

        if(key.compareTo(node.key) < 0) {
            node.left = remove(node.left,key);
            return node;
        } else if(key.compareTo(node.key) > 0) {
            node.right = remove(node.right,key);
            return node;
        } else { //e == node.e

            //左子树为空
            if(node.left == null) {
                Node rightNode =  node.right;
                node.right = null;
                size --;
                return rightNode;
            }

            //右子树为空
            if(node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size --;
                return leftNode;
            }

            //待删除节点左右子树均不为空
            //找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
            //用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = remoMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    }

    //寻找二插搜索树的最小元素节点,递归实现
    private Node minimum(Node node) {
        if(node.left == null)
            return node;
        return minimum(node.left);
    }

    //删除最小元素节点的递归实现
    private Node remoMin(Node node){
        if(node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size --;
            return rightNode;
        }

        node.left =remoMin(node.left);
        return node;
    }

    //返回以根节点为node的二分搜索树中，可以所在的节点
    private Node getNode(Node node, K key) {
        if(node == null)
            return null;
        if((key).compareTo(node.key) == 0)
            return node;
        else if((key).compareTo(node.key) < 0)
            return getNode(node.left,key);
        else
            return getNode(node.right,key);
    }

    @Override
    public boolean contains(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root,key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(root,key);
        if(node == null)
            throw new IllegalArgumentException(key+" is not exist");
        node.value = newValue;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163

测试程序

import java.util.ArrayList;
import java.util.Random;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
		ArrayList<String> arrayList = new ArrayList<>();
		arrayList.add("a");
		arrayList.add("b");
		arrayList.add("b");
		arrayList.add("c");
		arrayList.add("c");
		arrayList.add("c");
		arrayList.add("d");
		arrayList.add("d");
		arrayList.add("d");
		arrayList.add("d");
        //改成LinkedListMap可直接测试链表构成的映射
		BSTMap<String,Integer> bstMap = new BSTMap<>();
		for(String str : arrayList) {
    		if(bstMap.contains(str)) {
        		bstMap.set(str,bstMap.get(str)+1);
    		} else {
        		bstMap.add(str,1);
    		}
		}
		System.out.println(bstMap.getSize());
		System.out.println(bstMap.get("c"));
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

时间复杂度分析

在这里插入图片描述

映射的分类

  • 有序映射：有序映射中的键具有顺序性：基于搜索树实现
  • 无序映射：无序映射的键没有顺序性：基于哈希表实现
  • 多重映射：多重映射的键可以重复

集合和映射的关系

  • 基于集合可以实现映射
  • 基于映射可以实现集合（把value均设置为null）

在这里插入图片描述

leetcode中集合和映射的问题

java自带的set和map

  • TreeSet：java.util.TreeSet
  • TreeMap：java.util.TreeMap

两个数组的交集1

//两个数组中的交集元素,不包括重复元素
public static int[] intersection(int[] nums1, int[] nums2) {
    TreeSet<Integer> treeSet = new TreeSet<>();
    for(int nums : nums1)
        treeSet.add(nums);
    ArrayList<Integer> arrayList = new ArrayList<>();
    for(int i = 0; i<nums2.length ;i++) {
        if(treeSet.contains(nums2[i])){
            arrayList.add(nums2[i]);
            treeSet.remove(nums2[i]);
        }
    }
    int[] res = new int[arrayList.size()];
    for(int i = 0; i<res.length; i++)
        res[i] = arrayList.get(i);
    return res;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

两个数组的交集2

//两个数组中的交集元素,包括重复元素
public static int[] intersection1(int[] nums1,int[] nums2) {
    TreeMap<Integer,Integer> treeMap = new TreeMap<>();
    for(int nums : nums1) {
        if(!treeMap.containsKey(nums)) {
            treeMap.put(nums,1);
        } else {
            treeMap.put(nums,treeMap.get(nums)+1);
        }
    }
    ArrayList<Integer> arrayList = new ArrayList<>();
    for(int i=0; i<nums2.length; i++) {
        if(treeMap.containsKey(nums2[i])) {
            arrayList.add(nums2[i]);
            treeMap.put(nums2[i],treeMap.get(nums2[i])-1);
            if(treeMap.get(nums2[i]) == 0)
                treeMap.remove(nums2[i]);
        }
    }
    int[] res = new int[arrayList.size()];
    for(int i = 0; i<res.length; i++) {
        res[i] = arrayList.get(i);
    }
    return res;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/570906
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号