什么是键值表
键值表是键值对集合，相似字典，支持存入键值对，按键查值等操作。
对外接口
public void put(Key key, Value val);public Value get(Key key);public boolean contains(Key key);public Value remove(Key key);public int size();public boolean isEmpty();
接口代码
public interface IMap<Key, Value> {
/**
* 存入键值对
*
* @param key
* 键
* @param value
* 值
*/
public void put(Key key, Value value);
/**
* 按鍵查值
*
* @param key
* 鍵
* @return 值
*/
public Value get(Key key);
/**
* 推断是否包括某键
*
* @param key
* 键
* @return <code>true</code> 若包括；否则，<code>false</code>
*/
public boolean contains(Key key);
/**
* 删除键为key的键值对
*
* @param key
* 键
*/
public Value remove(Key key);
/**
* 返回键值对个数
*
* @return 键值对个数
*/
public int size();
/**
* 推断键值表是否为空
*
* @return <code>true</code> 假设键值表为空；否则，<code>false</code>。
*/
public boolean isEmpty();
}
0基础实现
package com.gmail.dailyefforts.ds;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class SimpleLinkedMap<Key, Value> implements IMap<Key, Value>{
private class Node {
private Node prev;
private Key key;
private Value val;
private Node next;
public Node(Node prev, Key key, Value val, Node next) {
this.prev = prev;
this.key = key;
this.val = val;
this.next = next;
}
@Override
public String toString() {
return String.format("%s=%s", String.valueOf(key),
String.valueOf(val));
}
}
private int size;
private Node first;
private Node last;
@Override
public void put(Key key, Value val) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
x.val = val;
return;
}
}
Node oldLast = last;
last = new Node(last, key, val, null);
if (oldLast != null) {
oldLast.next = last;
}
size++;
if (first == null) {
first = last;
}
}
@Override
public Value remove(Key key) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
if (x.prev == null) {
first = x.next;
} else {
x.prev.next = x.next;
}
if (x.next == null) {
last = x.prev;
} else {
x.next.prev = x.prev;
}
size--;
return x.val;
}
}
return null;
}
@Override
public boolean contains(Key key) {
return get(key) != null;
}
@Override
public Value get(Key key) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
return x.val;
}
}
return null;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append('{');
for (Node x = first; x != null; x = x.next) {
builder.append(x);
if (x.next != null) {
builder.append(", ");
}
}
builder.append('}');
return builder.toString();
}
public static void main(String[] args) {
final int N = 100 * 100;
SimpleLinkedMap<Integer, String> map = new SimpleLinkedMap<>();
Map<Integer, String> map2 = new HashMap<>();
for (int i = 0; i < N; i++) {
Integer key = Integer.valueOf(i);
String value = "item-" + i;
map2.put(key, value);
map.put(key, value);
}
// System.out.println(map2);
// System.out.println(map);
Random random = new Random(System.currentTimeMillis());
for (int i = 0; i < N / 2; i++) {
final int key = random.nextInt(N);
final String a = map.remove(key);
final String b = map2.remove(key);
if (a == null) {
assert (b == null);
} else {
assert (a.equals(b));
}
}
assert(map.size() == map2.size());
for (int i = 0; i < N; i++) {
final String a = map.get(i);
final String b = map2.get(i);
if (a == null) {
assert (b == null);
} else {
assert (a.equals(b));
}
}
}
}
Hash实现
在上面的0基础实现中。每次查询都要遍历了整个字典。效率为O(n)。现实中，我们从字典中查询某个单词时。我们借助索引来提高效率。而不是从该字典收录的第一个词開始逐个遍历整个字典。
我们能够利用hash来建立索引，遇到索引同样时再用链表存储。
package com.gmail.dailyefforts.ds;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class MyHashMap<Key, Value> implements IMap<Key, Value> {
private int size;
private static final int M = 100 * 100;
private SimpleLinkedMap<Key, Value>[] a = (SimpleLinkedMap<Key, Value>[]) new SimpleLinkedMap[M];
@Override
public void put(Key key, Value value) {
SimpleLinkedMap<Key, Value> map = map(key);
if (!map.contains(key)) {
size++;
}
map.put(key, value);
}
private int hash(Key key) {
// [0, M]
return key.hashCode() & 0x7fffffff % M;
}
private SimpleLinkedMap<Key, Value> map(Key key) {
int index = hash(key);
if (a[index] == null) {
a[index] = new SimpleLinkedMap<Key, Value>();
}
return a[index];
}
@Override
public Value get(Key key) {
return map(key).get(key);
}
@Override
public boolean contains(Key key) {
return map(key).contains(key);
}
@Override
public Value remove(Key key) {
Value value = map(key).remove(key);
if (value != null) {
size--;
}
return value;
}
@Override
public int size() {
return this.size;
}
@Override
public String toString() {
return super.toString();
}
@Override
public boolean isEmpty() {
return size() == 0;
}
public static void main(String[] args) {
final int N = 100 * 100 * 100;
MyHashMap<Integer, String> map = new MyHashMap<>();
Map<Integer, String> mapRef = new HashMap<>();
for (int i = 0; i < N; i++) {
Integer key = Integer.valueOf(i);
String value = "item-" + i;
map.put(key, value);
mapRef.put(key, value);
}
assert(map.size() == mapRef.size());
Random random = new Random(System.currentTimeMillis());
for (int i = 0; i < N / 2; i++) {
final int key = random.nextInt(N);
assert (map.contains(key) == mapRef.containsKey(key));
final String a = map.remove(key);
final String b = mapRef.remove(key);
if (a == null) {
assert (b == null);
} else {
assert (a.equals(b));
}
}
assert (map.size() == mapRef.size());
for (int i = 0; i < N; i++) {
final int key = random.nextInt(N);
final String a = map.get(key);
final String b = mapRef.get(key);
if (a == null) {
assert (b == null);
} else {
assert (a.equals(b));
}
}
System.out.println("test passed");
}
}