（八）数据结构之映射

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 558 | 阅读时长 ≈ 1 分钟
  此文待重构

简介

  映射，或者射影，在数学及相关的领域经常等同于函数。基于此，部分映射就相当于部分函数，而完全映射相当于完全函数。

  在很多特定的数学领域中，这个术语用来描述具有与该领域相关联的特定性质函数，例如，在拓扑学中的连续函数，线性代数中的线性变换等等。

  映射通过下图进行理解：

  即存储（键，值）数据对的数据结构 (Key,Value)，我们可以根据键 (Key) 来寻找值 (Value) 。

类别

  根据其底层实现的不同，分为链表映射、二叉树映射等等。

实现步骤

代码实现

链表实现

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
public class LinkedListMap<K, V> implements Map<K, V> {
    private class Node {
        public K key;
        public V value;
        public Node next;

        public Node() {

        }

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

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        this.dummyHead = new Node();
    }

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

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

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

    @Override
    public boolean contains(K key) {
        return getNode(key) == null ? false : true;
    }

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

    @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)) {
                Node delNode = pre.next;
                pre.next = delNode.next;
                delNode.next = null;
                size--;
                return delNode.value;
            }
            pre = pre.next;
        }
        return null;
    }

    @Override
    public void set(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            throw new IllegalArgumentException("doesn't exist");
        }
        node.value = value;
    }
}

二叉搜索树实现

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
public class BinarySearchTreeMap<K extends Comparable<K>, V> implements Map<K, V> {
    private class TreeNode {
        public K key;
        public V value;
        public TreeNode left, right;

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

    private TreeNode root;
    private int size;

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

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

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

    private TreeNode add(TreeNode treeNode, K key, V value) {
        if (treeNode == null) {
            size++;
            treeNode = new TreeNode(key, value);
        } else if (key.compareTo(treeNode.key) < 0) {
            treeNode.left = add(treeNode.left, key, value);
        } else if (key.compareTo(treeNode.key) > 0) {
            treeNode.right = add(treeNode.right, key, value);
        } else {
            treeNode.value = value;
        }
        return treeNode;
    }

    public TreeNode getTreeNode(TreeNode treeNode, K key) {
        if (treeNode == null) {
            return null;
        }
        if (key.compareTo(treeNode.key) == 0) {
            return treeNode;
        } else if (key.compareTo(treeNode.key) < 0) {
            return getTreeNode(treeNode.left, key);
        } else {
            return getTreeNode(treeNode.right, key);
        }
    }

    @Override
    public V get(K key) {
        TreeNode treeNode = getTreeNode(root, key);
        return treeNode == null ? null : treeNode.value;
    }

    @Override
    public boolean contains(K key) {
        return getTreeNode(root, key) == null ? false : true;
    }

    @Override
    public void set(K key, V value) {
        TreeNode treeNode = getTreeNode(root, key);
        if (treeNode != null) {
            treeNode.value = value;
        } else throw new IllegalArgumentException(key + "doesn't exist");
    }


    private TreeNode getMiniumTreeNode(TreeNode node) {
        if (node.left == null) {
            return node;
        }
        return getMiniumTreeNode(node.left);
    }

    // 删除以treeNode为根的二叉搜索树的最小节点
    // 返回删除最小节点后的树
    private TreeNode removeMiniumTreeNode(TreeNode treeNode) {
        if (treeNode.left == null) {
            TreeNode rightTreeNode = treeNode.right;
            treeNode.right = null;
            size--;
            return treeNode;
        }
        treeNode.left = removeMiniumTreeNode(treeNode.left);
        return treeNode;
    }

    @Override
    public V remove(K key) {
        TreeNode treeNode = getTreeNode(root, key);
        if ((treeNode != null)) {
            root = remove(root, key);
            return treeNode.value;
        }
        return null;
    }

    private TreeNode remove(TreeNode treeNode, K key) {
        if (treeNode == null) {
            return null;
        }
        if (key.compareTo(treeNode.key) < 0) {
            treeNode.left = remove(treeNode.left, key);
            return treeNode;
        } else if (key.compareTo(treeNode.key) > 0) {
            treeNode.right = remove(treeNode.right, key);
            return treeNode;
        } else {
            if (treeNode.left == null) {
                TreeNode rightTreeNode = treeNode.right;
                treeNode.right = null;
                size--;
                return rightTreeNode;
            }
            if (treeNode.right == null) {
                TreeNode leftTreeNode = treeNode.left;
                treeNode.left = null;
                size--;
                return leftTreeNode;
            }

            TreeNode successor = getMiniumTreeNode(treeNode);
            successor.right = removeMiniumTreeNode(treeNode);
            successor.left = treeNode.left;
            treeNode.left = treeNode.right = null;
            return successor;
        }
    }
}

时间复杂度分析

操作 链表实现映射 二叉树实现映射 平均 最差
add O(n) O(h) O(log n) O(n)
remove O(n) O(h) O(log n) O(n)
set O(n) O(h) O(log n) O(n)
get O(n) O(h) O(log n) O(n)
contains O(n) O(h) O(log n) O(n)

文章信息

时间 说明
2018-12-10 初稿
0%