HashMap的简单实现

基本概念

Map 别名映射表，也叫关联数组，基本思想是它维护的键-值(对)关联，因此可以用键查找值，也有放入键值的操作，下面根据定义自己来实现一个Map,首先应该想到的是数组，因为大多数Java集合类底层都是基于数组和链表的，这里我给它命名叫做 MapVersion01

 1 public class MapVersion01<K,V> {
 2     //存储每一个键值对的数组
 3     private Object[][] pairs;
 4     //数组的容量
 5     private int index;
 6 
 7     public MapVersion01(int capacity) {
 8         this.pairs = new Object[capacity][2];
 9     }
10 
11     /**
12      * 插入的方法
13      * @param key
14      * @param value
15      */
16     public void  put(K key, V value) {
17         if(index >= pairs.length)
18             throw new IndexOutOfBoundsException();
19         pairs[index++] = new Object[]{key, value};
20     }
21 
22     /**
23      * 查找方法
24      * @param key
25      * @return
26      */
27     public V get(K key) {
28         for(int i = 0 ; i < index ; i++) {
29             if(key.equals(pairs[i][0]))
30                 return (V)pairs[i][1];
31         }
32         return null;
33     }
34 
35     @Override
36     public String toString() {
37         StringBuilder sb = new StringBuilder();
38         for(int i = 0 ; i < index ; i ++) {
39             sb.append(pairs[i][0]).toString();
40             sb.append(" : ");
41             sb.append(pairs[i][1].toString());
42             if(i < index - 1) {
43                 sb.append("
");
44             }
45         }
46         return sb.toString();
47     }
48 
49     public static void main(String[] args) {
50         MapVersion01<Integer,String> map = new MapVersion01<Integer,String>(10);
51         map.put(1,"111");
52         map.put(2,"222");
53         map.put(3,"333");
54         map.put(4,"444");
55         map.put(5,"555");
56         map.put(6,"666");
57         System.err.println(map);
58     }
单元测试结果:

这里为了方便查看，重写了toString方法，打印出每一个键值对儿，乍一看，实现起来貌似很简单，再看一下Map接口，好像少了点什么。对了，少了2样东西:

遍历hash表取键值对的方法；
分别得到所有键的集合、值的集合；

这2个问题应该很好实现,下面是我实现的:

 1 public Set<K> keySet() {
 2     Set<K> keySet = new HashSet<K>();
 3     if (pairs.length > 0) {
 4         for (int i = 0; i < index; i++) {
 5             K key = (K) pairs[i][0];
 6             keySet.add(key);
 7         }
 8     }
 9     return keySet;
10 }
11 
12 public Set<V> values() {
13     Set<V> values = new HashSet<V>();
14     if (pairs.length > 0) {
15         for (int i = 0; i < index; i++) {
16             V value = (V) pairs[i][1];
17             values.add(value);
18         }
19     }
20     return values;
21 }
22 
23 public Set<Entry<K, V>> entrySet() {
24     Set<Entry<K, V>> set = new HashSet<Entry<K, V>>();
25     if (pairs.length > 0) {
26         for (int i = 0; i < index; i++) {
27             K key = (K) pairs[i][0];
28             V value = (V) pairs[i][1];
29             Entry<K, V> entry = new Entry<K, V>(key, value);
30             set.add(entry);
31         }
32     }
33     return set;
34 }
35 
36 //键值对存放在一起的映射对象
37 private static class Entry<K, V> {
38     private K key;
39     private V value;
40 
41     public Entry(K key, V value) {
42         this.key = key;
43         this.value = value;
44     }
45 
46     public K getKey() {
47         return key;
48     }
49 
50     public void setKey(K key) {
51         this.key = key;
52     }
53 
54     public V getValue() {
55         return value;
56     }
57 
58     public void setValue(V value) {
59         this.value = value;
60     }
61 
62     @Override
63     public int hashCode() {
64         return (key == null ? 0 : key.hashCode()) ^ (value == null ? 0 : value.hashCode());
65     }
66 
67     @Override
68     public boolean equals(Object obj) {
69         if (!(obj instanceof Entry))
70             return false;
71         Entry<K, V> me = (Entry<K, V>) obj;
72         return (me.getKey() == null ? key == null : me.getKey().equals(key)) &&
73                 (me.getValue() == null ? value == null : me.getValue().equals(value));
74     }
75 }