JAVA_12

JAVA容器HashMap

1.HashMap

底层实现采用了哈希表，这是一种非常重要的数据结构。
对于我们以后理解很多技术都非常有帮助(比如:redis 数据库的核心技术和 HashMap 一样)，因此，非常有必要理解。

2.数据结构中由数组和链表来实现对数据的存储，他们各有特点。

(1)数组:占用空间连续。寻址容易，查询速度快。但是，增加和删除效率非常低。
(2)链表:占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。
那么，我们能不能结合数组和链表的优点(即查询快，增删效率也高)呢?答案就是“哈希表”。哈希表的本质就是“数组+链表”

3.equals和hashcode通常需要一起重写!

equals为true，那么hashcode必须相等(主要就是为了HashMap。如果不这么规定，HashMap存取的时候就有悖论了!)

4.手写HashMap

package obj.src.lz;import java.util.HashMap;/*** 自定义map接口* @param <K>* @param <V>*/
public interface MyMap<K,V> {public void put(K key,V value);public V get(K key);public boolean containsKey(K key);public boolean containValue(V value);public void remove(K key);public int size();public boolean isEmpty();}

5.手写MyHashMap

package obj.src.lz;import java.util.Arrays;/*** 手工实现HashMap** @param <K>* @param <V>*/
public class MyHashMap<K, V> implements MyMap<K, V> {private static final int INITIAL_CAPACITY = 16;private int size;private Entry[] table;public MyHashMap() {table = new Entry[INITIAL_CAPACITY];}public static void main(String[] args) {MyMap<String, String> map = new MyHashMap<>();System.out.println(map.size());map.put("a", "123");map.put("a", "124");map.put("b", "1234");map.put("c", "12345");String b = map.get("b");System.out.println(b);map.remove("b");System.out.println(map);}@Overridepublic String toString() {
//        return "MyHashMap{" +
//                "size=" + size +
//                ", table=" + Arrays.toString(table) +
//                '}';StringBuilder sb = new StringBuilder();sb.append("[");//思考：怎么去掉最后一个,
//        for (Entry e : table) {
//            while (e != null) {
//                sb.append("{" + e.key + ":" + e.value + "},");
//                e = e.next;
//            }
//        }boolean first = true;for (Entry<K, V> e : table) {while (e != null) {if (!first) {sb.append(", ");}sb.append("{").append(e.key).append(":").append(e.value).append("}");first = false; e = e.next;}}sb.append("]");return sb.toString();}@Overridepublic void put(K key, V value) {int index = hash(key);Entry entry = new Entry(key, value, index, null);if (table[index] == null) {table[index] = entry;} else {Entry e = table[index];Entry last = e;while (e != null) {if (e.key.equals(key)) {e.value = value;//key相等，则覆盖valuereturn;}last = e;e = e.next;}last.next = entry;}size++;}public int hash(Object key) {int hashcode = key.hashCode();//返回int，可能时负数hashcode = hashcode < 0 ? -hashcode : hashcode;//        int index = hashcode % table.length;//早期jdk就是这样做的int index = hashcode & (table.length - 1);//位运算，效率高return index;}@Overridepublic V get(K key) {int index = hash(key);while (table[index] != null) {Entry e = table[index];while (e != null) {if (e.key.equals(key)) {return (V) e.value;}e = e.next;}}return null;}@Overridepublic boolean containsKey(K key) {return false;}@Overridepublic boolean containValue(V value) {return false;}@Overridepublic void remove(K key) {int index = hash(key);if (table[index] != null) {Entry e = table[index];Entry previous = null;while (e != null) {if (e.key.equals(key)) {if (previous == null) {//说明是第一个节点table[index] = e.next;} else {previous.next = e.next;}size--;}previous = e;e = e.next;}}}@Overridepublic int size() {return size;}@Overridepublic boolean isEmpty() {return size == 0;}
}class Entry<K, V> {K key;V value;int hash;Entry next;public Entry(K key, V value, int hash, Entry next) {this.key = key;this.value = value;this.hash = hash;this.next = next;}public Entry() {}
}