1.关于Map和HashMap
这两个东西想必大家都很熟悉了，简单的概括就是：面试中会问到、笔试中会考到、开发中会用到。
那么有关这块知识呢，大家可以参考我的这几篇文章：
2.案例代码
要求是这样的：
请完善TestMap类，要求只实现get、put、remove、size四个方法
-要求不能使用第三方包，不能使用JDK中Map实现类
- 请对完成的方法进行测试，在main方法中调用验证
因为在Map这种K-V键值对的存储结构中，其实也是一个哈希表，那么它每个节点都有自己的 key、value、hash值、指向下一个节点的指针，所以我们也需要定义一个内部类来存储这些信息。
然后我们同时需要模仿jdk官方的Map接口，自定义我们自己的Map接口，其中包括一些常用方法。（具体的已经写在代码注释中了）
public interface Map<K, V> { int size(); boolean isEmpty(); boolean containsKey(Object key); boolean containsValue(Object value); V get(Object key); V put(K key, V value); V remove(Object key); void clear(); interface Entry<K, V> { K getKey(); V getValue(); } }
import java.util.Collection; import java.util.Set; public class TestMap<K, V> implements Map<K, V> { private static final int DEFAULT_INITIAL_CAPACITY = 16; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private float loadFactor = 0; private int initCapacity = 0; private Entry<K, V>[] table = null; private int size = 0; public TestMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; this.initCapacity = DEFAULT_INITIAL_CAPACITY; table = new Entry[this.initCapacity]; } // private int hash(K key) { // int h; // return (key == null) ? 0 : Math.abs((h = key.hashCode())) ^ (h >>> 16); // } @Override public int size() { return size; } @Override public V get(Object key) { Entry<K, V> e = null; //默认不存在 //计算哈希码 int hash = key.hashCode(); //计算存储的位置 int index = hash % table.length; //存储到指定的位置 if (table[index] != null) { //该位置存储了元素 Entry<K, V> entry = table[index]; //先指向第一个元素 while (entry != null) { //比较 if (entry.hash == hash && entry.getKey().equals(key)){ //找到了这个key e = entry; break; } //指向下一个结点,继续循环判断 entry = entry.next; } } return e == null ? null : e.value; } @Override public V put(K key, V value) { //计算哈希码 int hash = key.hashCode(); //计算存储的位置 int index = hash % table.length; //存储到指定的位置 if (table[index] == null) { //该位置还没有元素 table[index] = new Entry<K, V>(key, value, null, hash); ++size; } else { //该位置已经存储了元素 //查询是否存在相同key的Entry Entry<K, V> entry = table[index]; //指向链表的第一个元素 while (entry != null) { //比较 if (entry.hash == hash && entry.getKey().equals(key)){ //如果找到了相同的key,使用新的value将旧的value替换掉 entry.value = value; return entry.value; } //指向下一个结点,继续循环判断 entry = entry.next; } //如果没有相同的key,添加新的结点,下一个结点就是原来的第一个结点，也就是table[index],添加到链表的第一个位置(table[index]) table[index] = new Entry<K, V>(key, value, table[index], hash); ++size; } return value; } @Override public V remove(Object key) { //计算哈希码 int hash = key.hashCode(); //计算存储的位置 int index = hash % table.length; //先定义一个prev表示待删除的元素的上一个 Entry<K, V> prev = table[index]; Entry<K, V> e = prev; while (e != null) { //定位出e的下一个元素，当找到我们要删除的元素时，将链表切断，将prev和next连接即可。 Entry<K, V> next = e.next; //在链表上定位到这个元素，先判断hash值是否相等，再判断key的equals是否相等！ if(e.hash == hash && (e.key == key || (key != null && key.equals(e.key)))) { --size; //这里，还得判断一个东西，即定位到的这个Entry是否是table[i]，因为table[i]上的删除和链表上的删除有区别 if(prev == e) { table[index] = next; } else { prev.next = next; //如果不是table位置的，则是链表后边的元素，此时，将prev的下一个置为e的next即可，此时，e已被切断,e的前后Entry被连接起来 } return e.value; } //上边的if没进去，则执行下一次循环，指针向后移动一位！ prev = e; e = next; } return null; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean containsKey(Object key) { return get(key) != null; } @Override public boolean containsValue(Object value) { Entry<K, V>[] tab; V v; if ((tab = table) != null && size > 0) { for (Entry<K, V> e : tab) { for (; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; } @Override public void clear() { Entry<K, V>[] tab; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } } @Override public String toString() { StringBuilder sb = new StringBuilder("{"); for (int i = 0; i < table.length; i++) { //外层循环主数组 if (table[i] != null) { Entry<K, V> entry = table[i]; //让entry指向链表的第一个元素 while (entry != null) { //内层循环循环链表 sb.append(entry.key + " = " + entry.value + ", "); //指向下一个结点,继续循环判断 entry = entry.next; } } } if (size != 0){ //如果有元素就把最后一个逗号去掉 sb.deleteCharAt(sb.length() - 1); } sb.setCharAt(sb.length() - 1, '}'); return sb.toString(); } // HashMap中存储节点信息的数据结构 class Entry<K, V> implements Map.Entry<K, V> { K key; V value; Entry<K, V> next; int hash; //记录下标 Entry(K key, V val, Entry<K, V> next, int hash) { this.key = key; this.value = val; this.next = next; this.hash = hash; } @Override public K getKey() { return key; } @Override public V getValue() { return value; } } public static void main(String[] args) { TestMap<String, Object> map = new TestMap<>(); map.put("姓名", "张三"); map.put("年龄", "20"); map.put("性别", "男"); map.put("爱好", "打篮球"); System.out.println(map.get("姓名")); System.out.println(map); System.out.println("map集合中键值对数量为：" + map.size()); System.out.println("map集合中是否包含key：" + map.containsKey("姓名")); System.out.println("map集合中是否包含value：" + map.containsValue("小哥")); String s = (String) map.remove("性别"); System.out.println("移除的key对应的value值为：" + s); System.out.println("移除之后map集合中键值对数量为：" + map.size()); map.clear(); System.out.println("map集合是否为空：" + map.isEmpty()); } }
