Fork me on GitHub

Map及其底层简单实现

发表于 | 分类于 |
本文共计: 2,002 | 阅读耗时 ≈ 10

Map数据结构及其底层简单实现

其实Java中的map就是映射，叫字典也可以，其实map也是一种容器，在这里为了深入的去理解map这种数据结构，从底层自己简单的实现 一下。

使用链表作为底层基础来实现Map

其实链表这种数据结构我们知道其一般只包含next和value两个属性，但是其实你也可以多给他添加一个key的属性。这样的话就和我们的map这种数据结构很像了，具体的实现如下：

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
public class LinkedListMap <K,V> implements Map<K,V> {

    /**
     * 初始化链表
     * 没有泛型的
     */
    private class Node{
        public Node next;
        public K key;
        public V value;

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

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

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

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

    public Node dummyHead;   //虚拟头结点
    public int size;  //链表的大小

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

    /**
     * 获取size
     * @return
     */
    @Override
    public int getSize(){
        return size;
    }

    /**
     * 链表是否为空
     * @return
     */
    @Override
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 获取key对应的节点
     * @param key key
     * @return
     */
    private Node getNode(K key){
        Node cur = dummyHead.next;
        while (cur.next != null){
            if (cur.key.equals(key)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }


    /**
     * 查询树中包含某个key
     * @param key
     * @return
     */
    @Override
    public boolean contains(K key){
        return getNode(key) != null;
    }


    /**
     * 向Map中添加元素
     * @param key key
     * @param value value
     */
    @Override
    public void add(K key, V value){
        if (!contains(key)){
            Node prev = new Node(key,value);
            prev.next = dummyHead.next;
            dummyHead.next = prev;
            size ++;
        }
    }

    @Override
    public V remove(K key) {
        if (!contains(key)){
            throw new IllegalArgumentException("Error: Map do not contain this key");
        }

        Node prev = dummyHead;
        while (prev.next != null){
            if (prev.next.key.equals(key)){
                Node delNode  = prev.next;
                prev.next = delNode.next;
                delNode.next= null;
                size--;
                return delNode.value;
            }
            prev = prev.next;
        }
        return null;
    }


    /**
     * 更新key对应的value
     * @param key key
     * @param newValue newValue
     */
    public void set(K key, V newValue){
        Node node = getNode(key);
        if (node != null){
            node.value = newValue;
        }
        if(node == null)
            throw new IllegalArgumentException(key + " doesn't exist!");
    }

    /**
     * 获取key对应的value
     * @param key key
     * @return
     */
    @Override
    public V get(K key){
        return contains(key)? getNode(key).value : null;
    }
}

使用二分搜索树的思想来实现

其实二分搜索树和用链表的思想来实现map的道理是一样的，每个树节点除了原来的value,左孩子和右孩子，你再添加一个key的属性就可以了，具体的实现如下：

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
public class BSTMap<K extends Comparable<K>, V>  implements Map<K, V> {


    /**
     * 二分搜索树节点的实现
     */
    private class Node{
        public K key;
        public V value;
        public Node left;
        private Node right;

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

    public Node root;      //树的根节点
    public int size;       //树的大小

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

    /**
     * 树的大小
     */
    @Override
    public int getSize(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 添加元素
     * @param key
     * @param value
     */
   public void add(K key, V value){
        root = add(root, key, value);
   }

    /**
     * 递归的向node为节点的树中添加元素
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node add(Node node, K key, V value){
       if (node == null){
           size ++;
           return node = new Node(key,value);
       }
       if (key.compareTo(node.key) > 0){
           node.right = add(node.right,key,value);
       }else if (key.compareTo(node.key) < 0){
           node.left = add(node.left, key, value);
       }else {
           node.value = value;
       }
       return node;
    }

    /**
     * 递归查询key对应的节点
     * @param node
     * @param key
     * @return
     */
    private Node getNode(Node node,K key){
        if (node == null){
            return node;
        }
        if (node.key.equals(key)){
            return node;
        }else if (node.key.compareTo(key) > 0){
            return getNode(node.left, key);
        }else{
            return getNode(node.right, key);
        }
    }

    /**
     * 包含某个元素
     * @param key
     * @return
     */
    @Override
    public boolean contains(K key){
        return getNode(root,key)!= null;
    }

    /**
     * 获取key对应的value
     * @param key
     * @return
     */
    @Override
    public V get(K key){
        return contains(key)? getNode(root,key).value:null;
    }

    /**
     * 更新key 对应的value
     * @param key
     * @param newValue
     */
    @Override
    public void set(K key, V newValue){
        Node node = getNode(root, key);
        if (node == null){
            throw new IllegalArgumentException("Key don't exist");
        }
        node.value = newValue;
    }

    /**
     * 返回以node为根的子树最小值的节点
     * @param node
     */
     public Node minimum(Node node){
        if (node == null){
            return node;
        }
        else {
            return minimum(node.left);
        }
     }

    /**
     * 删除以node为根节点的树中的最小元素，并返回新的子树的根
     * @param node
     * @return
     */
     public Node removeMin(Node node){
         if (node.left == null){
             Node delNode = minimum(node);
             node.left = delNode.right;
             delNode.right = null;
             size--;
             return node;
         }
        node.left =  removeMin(node.left);
         return node;
     }


    /**
     * 删除key对应的节点，并返回该key对应的值
     * @param key
     * @return
     */
    @Override
     public V remove(K key){
         return contains(key)?remove(root, key).value: null;
     }

    /**
     * 删除以node为子节点的树的值，并返回新的子树的根
     * @param node
     * @param key
     * @return
     */
     private Node remove(Node node, K key){

         if (node == null){
             return null;
         }

         if (key.compareTo(node.key) > 0){
             node.right = remove(node.right, key);
             return node;
         } else if (key.compareTo(node.key) < 0){
             node.left = remove(node.left, key);
             return node;
         }else {
             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);
             successor.left = node.left;
             successor.right = removeMin(node.right);
             node.left = null;
             node.right = null;
             return successor;
         }
     }
}

复杂度分析

使用二分搜索树和使用链表来实现map他的时间复杂度是不同的，因为这两种数据结构是不一样的，对于不同具体的是怎样的？如下表：

LinkListMap BSTMap BSTMap BSTMap
严格讲(h树的深度) 平均 最差
增add O(n) O(h) O(logn) O(n)
删remove O(n) O(h) O(logn) O(n)
改set O(n) O(h) O(logn) O(n)
查get O(n) O(h) O(logn) O(n)
查contains O(n) O(h) O(logn) O(n)

其实对于正常情况下，链表因为一般从头到尾需要遍历一遍，一般对应的操作的时间复杂度是O(n)的；

对于二分搜索树，其实操作一般是二分查找，时间复杂度是和树的深度是相关的，所以是O(logn)的，但是也不排除特殊情况，当一棵树退化成链表的时候如下：这时候他的时间复杂度也就和链表是一样的了。

应用

在LeetCode上有这么一道题目

1
2
3
4
5
6
7
8
9
10
Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

这里使用map这种数据结构去来处理这个问题，其实就是把一个数组中的元素放入map中作为key,以为key是不可重复的，然后数组中有重复元素怎么办？就value这个属性存放元素的个数。然后不断地查询另一个数组中的元素在map中的数量，找到一个就存一个，然后map中该元素对应的数量就减一个，具体的实现就如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class MapSolution {

    public int[] intersection(int[] nums1, int[] nums2) {

        TreeSet<Integer> set = new TreeSet();
        for (int num : nums1){
            set.add(num);
        }

        List<Integer> list = new ArrayList<>();
        for (int num : nums2){
            if (set.contains(num)){
                list.add(num);
                set.remove(num);
            }
        }
        int[] a = new int[list.size()];
        for (int i = 0; i < list.size(); i++){
            a[i] = list.get(i);
        }
        return a;
    }
}

本文标题:Map及其底层简单实现

文章作者:WilsonSong

发布时间:2018年06月08日 - 15:06

最后更新:2018年08月27日 - 14:08

原始链接:https://songwell1024.github.io/2018/06/08/Map/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------本文结束感谢您的阅读-------------