自己实现一个简单版的HashMap
HashMap简介
HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。 HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。 HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。 通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
简单版：
1package main.java.MyHashMap;
2
3/**
4 * Created with IntelliJ IDEA.
5 * User: lida
6 * Date: 2018/7/23
7 * To change this template use File | Settings | File Templates.
8 */
9public class MyHashMap<K, V> {
10 private static int default_length = 16;
11 private MyEntry<K, V>[] entries;
12
13 public MyHashMap() {
14 super();
15 entries = new MyEntry[default_length];
16 }
17
18 public V put(K key, V value) {
19 int index = key.hashCode() % default_length;// hascode值除map大小取余
20 MyEntry<K, V> prevoius = entries[index];
21 for (MyEntry<K, V> entry = entries[index]; entry != null; entry = entry.next) {
22 if (entry.getKey().equals(key)) {
23 V oldValue = (V) entry.getValue();
24 entry.setValue(value);
25 return oldValue;
26 }
27 }
28 MyEntry<K, V> entry = new MyEntry<>(key, value);
29 entry.next = prevoius;
30 entries[index] = entry;
31 return null;
32 }
33
34 public K get(K key){
35 int index= key.hashCode()%default_length;
36 for (MyEntry<K,V> entry= entries[index];entry!=null;entry=entry.next){
37 if(entry.getKey().equals(key)){
38 return (K)entry.getValue();
39 }
40 }
41 return null;
42 }
43
44 private final class MyEntry<K, V> {
45 private K key;
46 private V value;
47 private MyEntry next;
48
49 public MyEntry() {
50 super();
51 }
52
53 public MyEntry(K key, V value) {
54 super();
55 this.key = key;
56 this.value = value;
57 }
58
59 public MyEntry(K key, V value, MyEntry next) {
60 super();
61 this.key = key;
62 this.value = value;
63 this.next = next;
64 }
65
66 public K getKey() {
67 return key;
68 }
69
70 public void setKey(K key) {
71 this.key = key;
72 }
73
74 public V getValue() {
75 return value;
76 }
77
78 public void setValue(V value) {
79 this.value = value;
80 }
81
82 public MyEntry getNext() {
83 return next;
84 }
85
86 public void setNext(MyEntry next) {
87 this.next = next;
88 }
89 }
90}复杂版：
1package main.java.MyHashMap1;
2
3/**
4 * Created with IntelliJ IDEA.
5 * User: lida
6 * Date: 2018/7/23
7 * To change this template use File | Settings | File Templates.
8 */
9public class MyHashMap {
10 //默认初始化大小 16
11 private static final int DEFAULT_INITIAL_CAPACITY = 16;
12 //默认负载因子 0.75
13 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
14
15 //临界值
16 private int threshold;
17
18 //元素个数
19 private int size;
20
21 //扩容次数
22 private int resize;
23
24 private MyEntry[] table;
25
26 public MyHashMap() {
27 table = new MyEntry[DEFAULT_INITIAL_CAPACITY];
28 threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
29 size = 0;
30 }
31
32 private int index(Object key) {
33 //根据key的hashcode和entry长度取模计算key在entry中的位置
34 return key.hashCode() % table.length;
35 }
36
37 public void put(Object key, Object value) {
38 //key为null时需要特殊处理，为简化实现忽略null值
39 if (key == null) return;
40 int index = index(key);
41 //遍历index位置的entry，若找到重复key则更新对应entry的值，然后返回
42 MyEntry entry = table[index];
43 while (entry != null) {
44 if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
45 entry.setValue(value);
46 return;
47 }
48 entry = entry.getNext();
49 }
50 //若index位置没有entry或者未找到重复的key，则将新key添加到table的index位置
51 add(index, key, value);
52 }
53
54 private void add(int index, Object key, Object value) {
55 //将新的entry放到table的index位置第一个，若原来有值则以链表形式存放
56 MyEntry entry = new MyEntry(key, value, table[index]);
57 table[index] = entry;
58 //判断size是否达到临界值，若已达到则进行扩容，将table的capacicy翻倍
59 if (size++ >= threshold) {
60 resize(table.length * 2);
61 }
62 }
63
64 private void resize(int capacity) {
65 if (capacity <= table.length) return;
66
67 MyEntry[] newTable = new MyEntry[capacity];
68 //遍历原table，将每个entry都重新计算hash放入newTable中
69 for (int i = 0; i < table.length; i++) {
70 MyEntry old = table[i];
71 while (old!=null){
72 MyEntry next = old.getNext();
73 int index = index(old.getKey());
74 old.setNext(newTable[index]);
75 newTable[index] = old;
76 old=next;
77 }
78 }
79 //用newTable替table
80 table = newTable;
81 //修改临界值
82 threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);
83 resize++;
84 }
85
86 public Object get(Object key){
87 //这里简化处理，忽略null值
88 if (key == null) return null;
89 MyEntry entry= getEntry(key);
90 return entry == null ? null : entry.getValue();
91 }
92
93 public MyEntry getEntry(Object key){
94 MyEntry entry =table[index(key)];
95 while (entry!=null){
96 if (entry.getKey().hashCode()==key.hashCode()&&(entry.getKey()==key||entry.getKey().equals(key))){
97 return entry;
98 }
99 entry = entry.getNext();
100 }
101 return entry;
102 }
103 public void remove(Object key) {
104 if (key == null) return;
105 int index = index(key);
106 MyEntry pre = null;
107 MyEntry entry = table[index];
108 while (entry != null) {
109 if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {
110 if (pre == null) table[index] = entry.getNext();
111 else pre.setNext(entry.getNext());
112 //如果成功找到并删除，修改size
113 size--;
114 return;
115 }
116 pre = entry;
117 entry = entry.getNext();
118 }
119 }
120
121 public boolean containsKey(Object key) {
122 if (key == null) return false;
123 return getEntry(key) != null;
124 }
125
126 public int size() {
127 return this.size;
128 }
129
130 public void clear() {
131 for (int i = 0; i < table.length; i++) {
132 table[i] = null;
133 }
134 this.size = 0;
135 }
136
137
138 @Override
139 public String toString() {
140 StringBuilder sb = new StringBuilder();
141 sb.append(String.format("size:%s capacity:%s resize:%s\n\n", size, table.length, resize));
142 for (MyEntry entry : table) {
143 while (entry != null) {
144 sb.append(entry.getKey() + ":" + entry.getValue() + "\n");
145 entry = entry.getNext();
146 }
147 }
148 return sb.toString();
149 }
150}
151
152 final class MyEntry {
153 private Object key;
154 private Object value;
155 private MyEntry next;
156
157 public MyEntry(Object key, Object value, MyEntry next) {
158 this.key = key;
159 this.value = value;
160 this.next = next;
161 }
162
163 public Object getKey() {
164 return key;
165 }
166
167 public void setKey(Object key) {
168 this.key = key;
169 }
170
171 public Object getValue() {
172 return value;
173 }
174
175 public void setValue(Object value) {
176 this.value = value;
177 }
178
179 public MyEntry getNext() {
180 return next;
181 }
182
183 public void setNext(MyEntry next) {
184 this.next = next;
185 }
186 }本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读