Map即映射表:它存放的是键值对关联的对象。因此,可以通过键来查找值。
在了解Map之前,我们通过Map的概念,先思考几个问题:
- map如何存放键-值的?
- map如何确定键的唯一性?
- map如何通过键快速查找值?
- 自己如何实现一个简单的map?
抱着提出问题,解决问题的态度,让我们开始map之旅吧。
第一步:来实现一个能想到的最简单的Map
我能想到的最简单的map就是将key和value放入一个二维数组中,然后根据key去数组中循环查找value。
二话不说,开撸:
public class AssociativeArray<K, V> {
//定义pairs二维数组
private Object[][] pairs;
private int index;
/**
* 定义固定长度的数组
* */
public AssociativeArray(int length) {
//pairs二维数组的长度是length,宽度为2
pairs = new Object[length][2];
}
public void put(K key, V value) {
if (index >= pairs.length) {
throw new ArrayIndexOutOfBoundsException();
}
//将key和value放入数组
pairs[index++] = new Object[]{key, value};
}
/**
* 根据key来查询value的值
* */
public V get(K key) {
for (int i = 0; i < index; i++) {
if (key.equals(pairs[i][0])) return (V) pairs[i][1];
}
return null;
}
/**
* 重写toString方法,输出map中的数据
* */
public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < index; i++) {
result.append(pairs[i][0].toString());
result.append(":");
result.append(pairs[i][1].toString());
if (i < index - 1) result.append("\n");
}
return result.toString();
}
public static void main(String[] args) {
//因为打算存5个元素,所以给数组固定一个长度为5
AssociativeArray<String,String> map = new AssociativeArray<>(5);
map.put("111","aaa");
map.put("222","bbb");
map.put("333","ccc");
map.put("444","ddd");
map.put("555","eee");
System.out.println(map);
System.out.println(map.get("333"));
}
}
上面的代码,输出结果符合预期,确实把对象对进去了,也取出来了。但是总感觉哪里不对?
- 首先,数组长度是固定的,我怎么可能每次都知道要传入的数组长度呢?
- 再有,每次根据key取value值,都要将数组循环一边,那要是这个数组很大,这性能差的要死啊。
- 最后,这个代码实在很low,一点也不高大上呀。
散列码和hashCode()
为了解决性能问题,HashMap使用了特殊值,散列码,来取代对键的缓慢搜索。
那什么是散列码呢?
散列码是:”相对唯一“的,用以代表对象的int值,它是通过将该对象的某些信息进行转换后由hashCode()生成的。
先来看一下不用散列码的例子:一个优秀的射击运动员在训练,向靶子射击10枪,设计完成后,想查看自己某一枪是否命中。
public class Shoot {
protected int number; //射击次数
public Shoot(int n){this.number = n;}
public String toString(){
return "Shoot # " + number;
}
}
public class Points {
private static Random ran = new Random();
//假设0-10环为命中,其他为脱靶
private boolean shadow = ran.nextInt(20) < 10 && ran.nextInt(20) > 0;
public String toString(){
if (shadow) return "命中!";
else return "脱靶!";
}
}
AssociativeArray
类的main方法稍加改动
public static void main(String[] args) {
AssociativeArray<Groundhog,Prediction> map = new AssociativeArray<>(10);
for (int i = 0;i<10;i++){
map.put(new Shoot(i),new Points());
}
//打印map中的值
System.out.println(map);
//查看第三次射击是否命中,这时候发现输出是null
System.out.println(map.get(new Shoot(2)));
}
在打印map的值时,可以看到KEY中明明有2这个键,可为什么map.get(new Shoot(2))
输出是null呢?
原因:问题出在Shoot自动地继承自基类Object,所以这里使用Object的
hashCode()
方法生成散列码,而他默认是使用对象的地址计算散列码。因此,由new Shoot(2)生成的第一个实例的散列码与由new Shoot(2)生成的第二个实例的散列码是不同的,而我们正是使用后者进行查找的。
public class Shoot {
protected int number; //射击次数
public Shoot(int n){this.number = n;}
public String toString(){
return "Shoot # " + number;
}
//重写hashCode()方法,用number作为散列码
public int hashCode(){return number;}
//重写equles方法,默认的equals()只是比较对象的地址
public boolean equals(Object o){
return o instanceof Shoot && (number == ((Shoot)o).number);
}
}
在Shoot
射击类中重写Object的hashCode()
和equals(Object o)
后,就可以正常查找射击是否命中了。
再写一个Map
我们知道了数组实现map的缺点,又了解了散列码和hashCode(),现在我们根据这些信息,让我们再实现一个更加完善的map吧。
public class SlowMap<K, V> extends AbstractMap<K, V> {
private List<K> keys = new ArrayList<K>();
private List<V> values = new ArrayList<V>();
public V put(K key, V value) {
V oldValue = get(key);
if (!keys.contains(key)) {
keys.add(key);
values.add(value);
} else values.set(keys.indexOf(key), value);
return oldValue;
}
public V get(Object key) {
if (keys.contains(key)) {
return values.get(keys.indexOf(key));
}
return null;
}
public V remove(Object key) {
if (keys.contains(key)) {
keys.remove(keys.indexOf(key));
}
return !keys.contains(key) ?
null : values.get(keys.indexOf(key));
}
public void clear() {
if(keys != null && keys.size() > 0){
keys = null;
values = null;
}
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K,V>> set = new HashSet<>();
Iterator<K> ki = keys.iterator();
Iterator<V> vi = values.iterator();
while (ki.hasNext()) set.add(new MapEntry<>(ki.next(),vi.next()));
return set;
}
public static void main(String[] args) {
SlowMap<Integer ,String > map = new SlowMap<>();
String[] chars =
"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
.split(" ");
for (int i = 0; i < chars.length; i++){
map.put(i,chars[i]);
}
System.out.println(map);
System.out.println("Map Size == " + map.size());
System.out.println(map.entrySet());
System.out.println(map.get(4));
System.out.println("删除元素: 【4】");
map.remove(4); //删除集合中的某个元素
System.out.println("Map Size == " + map.size());
//map.clear();//清空集合
System.out.println(map);
System.out.println(map.get(4));
}
}
public class MapEntry<K, V> implements Map.Entry<K, V> {
private K key;
private V value;
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V value) {
V reslut = value;
this.value = value;
return reslut;
}
public int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
public String toString(){return key + "=" + value;}
public MapEntry(K key, V value) {
this.key = key;
this.value = value;
}
}
分析代码:
SlowMap
类继承了AbstractMap
,又因为AbstractMap
实现了Map接口,这样SlowMap
就包含了Map借口的完整实现,继承AbstractMap
需要实现entrySet()
方法,entrySet()
是返回此映射中包含的映射关系的 set 视图集合。
在entrySet()
中使用的MapEntry
类作用是保存和读取键值,在entrySet()
中用来产生键值对的Set
这些代码看似很完美的模拟了map集合了,没毛病了~!
代码问题
- 问题出在Key和Value分别保存在了两个List集合中,整个类中
entrySet()
方法只是提供了Map的副本,而不是视图。 - 再有List集合移除元素的速度也是很不理想的。
总之,这个比用单纯的数组是强多了,但是还是有很多可以优化的地方。
优化性能的自定义Map
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
static final int SIZE = 997;
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
public V put(K key, V value) {
V oldValue = null;
//计算散列码 abs(int a),返回a的绝对值
int index = Math.abs(key.hashCode()) % SIZE;
//如果集合数组中没有元素,则初始化一个数组元素
if (buckets[index] == null) buckets[index] = new LinkedList<>();
//获取元素
LinkedList<MapEntry<K, V>> bucket = buckets[index];
MapEntry<K, V> pair = new MapEntry<>(key, value); //将存入KEY,VALUE值存入pair
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
while (it.hasNext()) {
MapEntry<K, V> iPair = it.next();
/**
* 对list中的值进行线性查询,解决冲突
* 既:当向数组集合中插入已经存在的key时,将会用新值的value替换原来的value值
* */
if (iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair);
found = true;
break;
}
}
if (!found) buckets[index].add(pair);
return oldValue;
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets == null) return null;
for (MapEntry<K, V> iPair : buckets[index]) {
if (iPair.getKey().equals(key)) return iPair.getValue();
}
return null;
}
public V remove(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets == null) return null;
for (MapEntry<K, V> iPair : buckets[index]) {
if (iPair.getKey().equals(key)) {
//如果存在key的键值,则删除
buckets[index].remove(iPair);
} else{
return iPair.getValue();
}
}
return null;
}
public void clear() {
if (buckets != null && buckets.length > 0) {
buckets = null;
}
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new HashSet<>();
if(buckets != null && buckets.length > 0){
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null) continue;
set.addAll(bucket);
}
}
return set;
}
public static void main(String[] args) {
SimpleHashMap<Integer, String> map = new SimpleHashMap<>();
String[] chars =
"A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
.split(" ");
for (int i = 0; i < chars.length; i++) {
map.put(i, chars[i]);
}
System.out.println(map.entrySet());
System.out.println("map的长度是:" + map.size() + " ,第7个元素是: " + map.get(6));
map.remove(6);
System.out.println("map的长度是:" + map.size());
System.out.println(map.get(6));
map.clear();
System.out.println(map.entrySet());
}
}
虽然还存在一点小瑕疵(在解决冲突方面的性能还是略微欠缺),基本上可以表达map的原理了…
总结回顾
HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。既向Map中存入键值对时,实际上是初始化一个数组。使用散列码可以根据key找到对应的value,散列码是在hashCode()中计算。
转载请注明:R&M » JAVA集合——Map原理浅析