1、什么是Map(映射)
存储( 键，值) 数据对的数据结构(Key,Value)
根据键（Key），寻找值(Value)
非常容易使用链表或者二分搜索树实现。
2、基于链表实现Map
public class LinkedListMap<K,V> implements IMap<K,V>{
private class Node<K,V>{
K key;
V value;
Node next;
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, value, null);
}
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;
}
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;
}
}
public V remove(K key) {
Node preNode = dummyHead;
while (preNode.next != null){
if(preNode.next.key.equals(key)){
break;
}else {
preNode = preNode.next;
}
}
if(preNode.next != null){
Node delNode = preNode.next;
preNode.next = delNode.next;
delNode.next = null;
size --;
return (V)delNode.value;
}
return null;
}
private Node getNode(K key){
Node cur = dummyHead.next;
while (cur != null){
if(cur.key.equals(key)){
return cur;
}else {
cur = cur.next;
}
}
return null;
}
public boolean contains(K key) {
return getNode(key) != null;
}
public V get(K key) {
Node node = getNode(key);
return node == null ? null : (V)node.value;
}
public void set(K key, V newValue) {
Node node = getNode(key);
if(node == null){
throw new IllegalArgumentException(key + " doesn't exist!");
}
node.value = newValue;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
测试：
public static void main(String[] args) {
//数据准备
ArrayList<String> list = new ArrayList<String>();
String[] arr = {"张三", "李四","王五", "赵六","张三丰","李思明","王老五","赵明"};
for(int i = 0; i < 10; i++){
for(String str : arr){
String key = str +i;
list.add(key);
}
}
for(int i = 0; i < 5000; i++){
for(String str : arr){
String key = str +i;
list.add(key);
}
}
System.out.println("准备的数据数量=" + list.size());
LinkedListMap<String, Integer> map = new LinkedListMap();
for(String key: list){
Integer value = map.get(key);
if(value == null){
map.add(key, 1);
}else {
map.add(key, value +1);
}
}
System.out.println("Map size: " + map.getSize());
String key = "张三0";
System.out.println(key + "出现的次数：" + map.get(key));
}
测试结果：
准备的数据数量=40080
Map size: 40000
张三0出现的次数：2
3、基于二分搜索树实现Map
public class BinarySearchTreeMap<K extends Comparable<K>, V> implements IMap<K,V>{
private class Node{
public K key;
public V value;
//左孩子
public Node left;
//右孩子
public Node right;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
//向二分搜索树中添加新的元素key,value
public void add(K key, V value){
root = add(root, key, value);
}
//向以node为根的二分搜索树种插入元素key,value，递归算法
public 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 { //key.compareTo(node.key) = 0
node.value = value;
}
return node;
}
//寻找最小节点
public K minimum(){
if(size == 0){
throw new IllegalArgumentException("Bst is empty");
}
return minimum(root).key;
}
//返回以Node为根的二分搜索树的最小值的节点
public Node minimum(Node node){
if(node.left == null){
return node;
}
return minimum(node.left);
}
// 从二分搜索树中删除最小值所在节点, 返回最小值
public K removeMin(){
K key = minimum();
root = removeMin(root);//注意这里，我们从root为根的树中删除掉了最小值，返回删除后的树的根节点，这个
//根节点就是新的root
return key;
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node){
// 递归的终止条件，当前节点没有左子树了，那么就是最小节点了
// 如果是最小节点，我们要做的是删除当前节点，但是当前节点很可能是有右子树的
// 我们先把该节点的右子树节点保存，然后就删除掉该右子树节点，最后把右子树节点返回即可
if(node.left == null){
Node rightNode = node.right;
node.right = null;//左节点为空了，让右子树也为空，相当于脱离了树
size --;
return rightNode;//返回右子树是为了后面的绑定操作
}
// 没有递归到底的情况，那么就递归调用其左子树，这个调用的过程会返回被删除节点的右子树，
//将返回的右子树重新绑定到上一层的node的左节点上就相当于彻底删除了那个元素
node.left = removeMin(node.left);
return node; // 删除后，根节点依然是node，返回即可
}
//从二分搜索树中删除元素为e的节点
public V remove(K key) {
Node node = getNode(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);
}
if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
} 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.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
return null;
}
public boolean contains(K key) {
return getNode(key) != null;
}
public V get(K key) {
Node node = getNode(key);
return node != null ? node.value : null;
}
public void set(K key, V newValue) {
Node node = getNode(key);
if(node == null){
throw new IllegalArgumentException(key + " doesn't exist");
}
node.value = newValue;
}
private Node getNode(K key){
return getNode(root, key);
}
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 { //if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
测试：
public static void main(String[] args) {
//数据准备
ArrayList<String> list = new ArrayList<String>();
String[] arr = {"张三", "李四","王五", "赵六","张三丰","李思明","王老五","赵明"};
for(int i = 0; i < 10; i++){
for(String str : arr){
String key = str +i;
list.add(key);
}
}
for(int i = 0; i < 5000; i++){
for(String str : arr){
String key = str +i;
list.add(key);
}
}
System.out.println("准备的数据数量=" + list.size());
BinarySearchTreeMap<String, Integer> map = new BinarySearchTreeMap();
for(String key: list){
Integer value = map.get(key);
if(value == null){
map.add(key, 1);
}else {
map.add(key, value +1);
}
}
System.out.println("Map size: " + map.getSize());
String key = "张三0";
System.out.println(key + "出现的次数：" + map.get(key));
}
输出结果：（和基于链表的Map结果一致，但是速度明显更快）
准备的数据数量=40080
Map size: 40000
张三0出现的次数：2
5、两种Map进行比较
public class TwoMapTest {
private static double testMap(IMap<String, Integer> map, ArrayList<String> list){
long startTime = System.nanoTime();
for(String key: list){
Integer value = map.get(key);
if(value == null){
map.add(key, 1);
}else {
map.add(key, value +1);
}
}
System.out.println("Map size: " + map.getSize());
String key = "张三0";
System.out.println(key + "出现的次数：" + map.get(key));
long endTme = System.nanoTime();
return (endTme - startTime) / 1000000000.0;
}
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
String[] arr = {"张三", "李四","王五", "赵六","张三丰","李思明","王老五","赵明"};
for(int i = 0; i < 10; i++){
for(String str : arr){
String key = str +i;
list.add(key);
}
}
for(int i = 0; i < 5000; i++){
for(String str : arr){
String key = str +i;
list.add(key);
}
}
System.out.println("准备的数据数量=" + list.size());
LinkedListMap<String, Integer> map1 = new LinkedListMap<String, Integer>();
double time1 = testMap(map1, list);
System.out.println("链表Map花费" + time1);
System.out.println("-------------------------------");
BinarySearchTreeMap<String, Integer> map2 = new BinarySearchTreeMap<String, Integer>();
double time2 = testMap(map2, list);
System.out.println("testMapSet花费" + time2);
}
}
输出结果如下：
准备的数据数量=40080 Map size: 40000 张三0出现的次数：2 链表Map花费12.458235521 ------------------------------- Map size: 40000 张三0出现的次数：2 testMapSet花费0.03265158
输出的结果一致，BinarySearchTreeMap的时间花费明显更少。
6、Map的时间复杂度分析
BinarySearchTreeMap最差情况为O(n),为了解决这个问题，后面引入了平衡二叉树
7、有序Map和无序Map
有序Map中的键具有顺序性，如基于搜索树实现的Map
无序Map中的键没有顺序性， 如这里基于链表的Map
8、多重Map
多重Map中的键可以重复。