自己实现HashMap集合

如图，HashMap的结果就是这个样子。横向是链表，纵向是数组。所以hashmap是由数组和链表组成的。
下面来实现HashMap
  1 import java.util.Collection;
  2 import java.util.Map;
  3 import java.util.Set;
  4 
  5 public class HashMapTemplate<K,V> implements Map<K,V>{
  6     //初始大小
  7      private int capacity = 16;  
  8      private int size = 0;  
  9      Entity<K,V>[] entities=null;
 10      
 11     @Override
 12     public void clear() {
 13         // TODO Auto-generated method stub
 14         entities=null;
 15     }
 16 
 17     @Override
 18     public boolean containsKey(Object key) {
 19         //处理key为null的情况
 20         if (key==null) {
 21             Entity entity=entities[0];
 22             if (entity==null) {
 23                 return false;
 24             }else {
 25                 if (entity.getKey()==key) {
 26                     return true;
 27                 }else{
 28                     while(entity.getNextEntity()!=null){
 29                         if (entity.getNextEntity().getKey().equals(key)) {
 30                             return true;
 31                         }
 32                         entity=entity.getNextEntity();
 33                     }
 34                     return false;
 35                 }
 36             }
 37         }else{
 38             int index=key.hashCode()%capacity;
 39             Entity entity=entities[index];
 40             if (entity.getKey().equals(key)) {
 41                 return true;
 42             }else {
 43                 while(entity.getNextEntity()!=null){
 44                     if (entity.getNextEntity().getKey().equals(key)) {
 45                         return true;
 46                     }
 47                     entity=entity.getNextEntity();
 48                 }
 49                 return false;
 50                 
 51             }
 52         }
 53     }
 54 
 55     @Override
 56     public boolean containsValue(Object value) {
 57         // TODO Auto-generated method stub
 58         return false;
 59     }
 60 
 61     @Override
 62     public Set<java.util.Map.Entry<K, V>> entrySet() {
 63         // TODO Auto-generated method stub
 64         return null;
 65     }
 66 
 67     @Override
 68     public V get(Object key) {
 69         if (key==null) {
 70             Entity entity=entities[0];
 71             if (entity.getKey()==key) {
 72                 return (V) entity.getValue();
 73             }else {
 74                 while(entity.getNextEntity()!=null){
 75                     if (entity.getNextEntity().getKey().equals(key)) {
 76                         return (V) entity.getValue();
 77                     }
 78                     entity=entity.getNextEntity();
 79                 }
 80                 return null;
 81                 
 82             }
 83         }else{
 84             int index=key.hashCode()%capacity;
 85             Entity entity=entities[index];
 86             if (entity.getKey().equals(key)) {
 87                 return (V) entity.getValue();
 88             }else {
 89                 while(entity.getNextEntity()!=null){
 90                     if (entity.getNextEntity().getKey().equals(key)) {
 91                         return (V) entity.getValue();
 92                     }
 93                     entity=entity.getNextEntity();
 94                 }
 95                 return null;
 96                 
 97             }
 98         }
 99     }
100 
101     @Override
102     public boolean isEmpty() {
103         // TODO Auto-generated method stub
104         return false;
105     }
106 
107     @Override
108     public Set<K> keySet() {
109         // TODO Auto-generated method stub
110         return null;
111     }
112 
113     @Override
114     public V put(K key, V value) {
115         reCapacity();  
116         Entity<K, V> newEntity = new Entity<K, V>(key, value);  
117         put(newEntity, this.entities, this.capacity); 
118         return null;
119     }
120     private void put(Entity<K, V> newEntity, Entity<K, V>[] entities, int capacity) {
121         if (newEntity.getKey()==null) {
122             Entity entity=entities[0];
123             if (entity==null) {
124                 entities[0]=newEntity;
125                 size++;
126             }
127         }else{
128             int index=newEntity.getKey().hashCode()%capacity;
129             Entity entity=entities[index];
130             Entity firstEntity =entities[index];
131             if (entity==null) {
132                 entities[index]=newEntity;
133                 size++;
134             }else {
135                 if (newEntity.getKey().equals(entity.getKey())) {
136                     newEntity.setNextEntity(entity.getNextEntity());
137                     newEntity.setPreEntity(entity.getPreEntity());
138                     if (entity.getNextEntity()!=null) {
139                         entity.getNextEntity().setPreEntity(newEntity);
140                     }
141                     entities[index]=newEntity;
142                 }else if (entity.getNextEntity()!=null) {
143                     while (entity.getNextEntity()!=null) {
144                           entity = entity.getNextEntity();  
145                             if (newEntity.getKey().equals(entity.getKey())) {  
146                                 newEntity.setPreEntity(entity.getPreEntity());  
147                                 newEntity.setNextEntity(entity.getNextEntity());  
148                                 if (entity.getNextEntity() != null) {  
149                                     entity.getNextEntity().setPreEntity(newEntity);  
150                                 }  
151                                 entities[index] = newEntity;  
152                             }  
153                     }
154                     newEntity.setNextEntity(firstEntity);  
155                     newEntity.setPreEntity(firstEntity.getPreEntity());  
156                     firstEntity.setPreEntity(newEntity);  
157                     entities[index] = newEntity;  
158                     size++;  
159                 }else {
160                      newEntity.setNextEntity(firstEntity);  
161                         firstEntity.setPreEntity(newEntity);  
162                         entities[index] = newEntity;  
163                         size++; 
164                 }
165             }
166         }
167      }
168     @Override
169     public void putAll(Map<? extends K, ? extends V> m) {
170         // TODO Auto-generated method stub
171         
172     }
173 
174     @Override
175     public V remove(Object key) {
176         // TODO Auto-generated method stub
177         return null;
178     }
179 
180     @Override
181     public int size() {
182         // TODO Auto-generated method stub
183         return this.size;
184     }
185 
186     @Override
187     public Collection<V> values() {
188         // TODO Auto-generated method stub
189         return null;
190     }
191     public HashMapTemplate() {  
192             //初始化容量
193             entities = new Entity[capacity];  
194     }
195     /**
196      * 扩容
197      */
198      private void reCapacity() {  
199             if (size >= capacity) {  
200                 int newCapacity = capacity * 2;  
201                 @SuppressWarnings("unchecked")  
202                 Entity<K, V>[] newEntities = new Entity[newCapacity];  
203                 for (int i = 0; i < capacity; i++) {  
204                     Entity<K, V> entity = entities[i];  
205                     while (entity != null) {  
206                         put(entity, newEntities, newCapacity);  
207                         entity = entity.getNextEntity();  
208                     }  
209                 }  
210                 this.capacity = newCapacity;  
211                 this.entities = newEntities;  
212             } 
213         }
214 
215     @Override
216     public String toString() {
217          StringBuilder sb = new StringBuilder();  
218             for (int i = 0; i < capacity; i++) {  
219                 sb.append("index=").append(i).append("[");  
220                 boolean hasEntity = false;  
221                 Entity<K, V> entity = entities[i];  
222                 if (entity != null) {  
223                     hasEntity = true;  
224                 }  
225                 while (entity != null) {  
226                     sb.append("[").append(entity.getKey()).append("=").append(entity.getValue()).append("]").append(",");  
227                     entity = entity.getNextEntity();  
228                 }  
229                 if (hasEntity) {  
230                     sb.deleteCharAt(sb.length() - 1);  
231                 }  
232                 sb.append("]
");  
233             }  
234             return sb.toString();  
235     }  
236 }
237 @SuppressWarnings("unchecked")
238 class Entity<K,V>{
239     private K key;
240     private V value;
241     private Entity<K,V> PreEntity;//前节点
242     private Entity<K,V> nextEntity;//后节点
243     
244     public K getKey() {
245         return key;
246     }
247     public void setKey(K key) {
248         this.key = key;
249     }
250     public V getValue() {
251         return value;
252     }
253     public void setValue(V value) {
254         this.value = value;
255     }
256     
257     public Entity getPreEntity() {
258         return PreEntity;
259     }
260     
261     public void setPreEntity(Entity preEntity) {
262         PreEntity = preEntity;
263     }
264     public Entity getNextEntity() {
265         return nextEntity;
266     }
267     public void setNextEntity(Entity nextEntity) {
268         this.nextEntity = nextEntity;
269     }
270     public Entity(K k,V v){
271         this.key=k;
272         this.value=v;
273     }
274     
275 }
上面有一个点需要注意一下：
1.HashMap允许key为null，所以需要处理一下
2.HashMap存放键值对的时候，需要检查容量是否充足，但是因为我们这里是引用传递，所以需要单独写一个put方法通过局部变量的临近原则解决对象的问题。
3.完成hashmap部分功能。并没有完全写完。