一、映射表(Map)简介
- 映射表是一种依照键/值对存储元素的容器,又称字典(directory),散列表(hash table)。
- 映射表将键和值一起保存,键类似于数组中的下标,不能有重复的键,每个键对应一个值
- 键和它对应的值构成一个条目。
二、链表实现映射表
package Map;
public class LinkedListMap<K, V> implements MyMap<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() {
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;
}
//获取键值key所对应的结点,这个方法为后续一些方法的实现提供了方便
public Node getNode(K key) {
Node current = dummyHead.next;
while(current != null) {
//这里不能用==,因为当key为字符串等时,判断将不准确
if(key.equals(current.key)) {
return current;
}
current = current.next;
}
return null;
}
//使用头插法向映射中添加条目
public void add(K key, V value) {
Node node = getNode(key);
if(node == null) { //映射中不存在键值为key的结点
Node newNode = new Node(key,value,dummyHead.next);
dummyHead.next = newNode;
size++;
}
else//映射中存在键值为key的结点,则更新value
node.value = value;
}
//查找键所对应条目是否在映射中
public boolean contains(K key){
Node node = getNode(key);
return node != null;
}
//删除键值key所对应的条目
public V remove(K key){
Node node = getNode(key);
if(node == null) //映射中不存在键值为key的条目
return null;
//映射中存在键值为key的条目
//1. 寻找要删除结点的前一个结点
Node prevNode = dummyHead;
while(prevNode.next != node) {
prevNode = prevNode.next;
}
//2. 将要删除的前一个结点和要删除结点的后一个结点相连
prevNode.next = node.next;
//3. 更新size
size--;
return node.value;
}
//获取键值为key的条目
public V get(K key){
Node node = getNode(key);
return (node == null) ? null : node.value;
}
//更新某一条目
public void set(K key, V newValue){
Node node = getNode(key);
//键所对应结点存在
if(node != null) {
node.value = newValue;
}
//键所对应结点不存在
else {
throw new IllegalArgumentException(key + "doesn't exists");
}
}
//获取映射表的大小
public int getSize(){
return size;
}
//判断映射表是否为空
public boolean isEmpty(){
return size == 0;
}
//测试
public static void main(String[] args) {
String str = "aaaaabbbbbbcccccdddddeeeee";
LinkedListMap<Character,Integer> map = new LinkedListMap<>();
for(int i = 0; i < str.length(); i++) {
char key = str.charAt(i);
if(map.contains(key)) {
map.set(key, map.get(key) + 1);
}
else {
map.add(key, 1);
}
}
System.out.println("a : " + map.get('a'));
System.out.println("b : " + map.get('b'));
System.out.println("c : " + map.get('c'));
System.out.println("d : " + map.get('d'));
System.out.println("e : " + map.get('e'));
}}