[数据结构与算法]集合基础-Map

Map是一个接口，其包含了多个实现类。Map是利用键值对的方式，来存储的。Key相当于扩大了索引的内容，不再局限于数组中的数字。

?HashMap

HashMap的底层实现采用了Hash表，这是一种非常重要的数据结构。key的hashcode值用于分割其在Entry[]中的位置，并在后面存储数据。具有极快的访问速度，但是其遍历顺序却是不确定的(因为在Hashmap的散列里，我们利用的散列方法会导致其遍历顺序的变化)。HashMap最多只允许记录一条键为null的记录。同时HashMap非线程安全的。如果想满足线程安全，可以使用synchronizedMap或者ConcurrentHashMap。

??????? HashMap在Java7中的实现是利用的一个数组+链表。数组中每个元素都是一个单向链表

??????? 而HashMap为了进一步提高效率，在Java8中，引入了红黑树。

HashMap在Java8中引入了红黑树，当链表的长度大于8之后，Java就会自动将链表转换成红黑树。将此前查找的时间复杂度由O(n)下降到了O(logn)

?

下面我们实现一种最基础的数组加链表形式的Map。分别要实现其put ，get 功能，并且要保证Key的唯一性。同时，我们重写toString方法，方便我们遍历整个Map。并且使用泛型操作。

package 集合.Map.手写HashMap;

import java.util.Arrays;

/**
 * @program:多线程和IO
 * @descripton:
 * @author:ZhengCheng
 * @create:2021/10/11-19:43
 **/
public class HashMap_ <T,E>{
    private Node[] Entry ;
    private int size ;
    public HashMap_() {
        init();
    }

    private void init() {
        size = 16;
        Entry = new Node[size];
    }
    //key对应的HashCode
    private int gethashCode(T key){
        return key.hashCode();
    }
    public void put(T key,E val){
        int hash = gethashCode(key);
        int index = getPosition(hash);

        if (Entry[index] == null){
            Entry[index] = new Node(hash,key,val);
        }else {
            //遍历列表判断是否冲突
            Node check = checkHash(hash,index);
            if (check == null){
                Node temp = Entry[index];
                while (temp.next == null){
                    temp.next = new Node(hash,key,val);
                }
            }else {
                System.out.println("冲突，添加失败");
                return;
            }
        }
    }

    private Node checkHash(int hash ,int index) {
         Node temp = Entry[index];
         while (temp.next!=null && temp.getHash()!=hash){
             temp = temp.next;
         }
         if (temp.next == null && temp.getHash() !=hash){
             return null;
         }
         return temp;
    }

    private int getPosition(int hash){
        return hash&(size-1);
    }
    public E get(T key){
        int hash = gethashCode(key);
        //比较有无hash？如何快速比较呢？没有方法
        int index = getPosition(hash);
        Node temp =checkHash(hash,index);
        if (temp != null){
            E v = (E) temp.getVal();
            return v;
        }else {
            System.out.println("无");
        }
        return null;
    }
    //方便查看map里的键值对内容  遍历数组遍历链表
    @Override
    public String toString() {
        String res = "";
        for (int i = 0; i < Entry.length; i++) {
            if (Entry[i] != null){
                //遍历链表
                Node tmp = Entry[i];
                while (tmp.next != null){
                    res += tmp.toString();
                    tmp = tmp.next;
                }
                res += tmp.toString();
            }
        }
        return res;
    }
}
class Node <T,E>{
    public int hash;
    private T key;
    private E val;
    public Node next ;

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }

    public E getVal() {
        return val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", val=" + val +
                '}';
    }

    public void setVal(E val) {
        this.val = val;
    }

    public Node(int hash, T key, E val) {
        this.hash = hash;
        this.key = key;
        this.val = val;
    }
}

public class testDemo {
    public static void main(String[] args) {
        HashMap_<Integer, Integer> map = new HashMap_<>();
        map.put(1,23);
        map.put(1,22);
        map.put(2,1);
        map.put(3,1);
        map.put(4,1);

        Integer i = map.get(1);
        System.out.println(i);
        System.out.println(map);
    }
}

冲突，添加失败
23
Node{key=1, val=23}Node{key=2, val=1}Node{key=3, val=1}Node{key=4, val=1}

Process finished with exit code 0

TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;

TreeMap实现了SortedMap接口（实现了NavigatableMap ，NM是实现了Sorted的），能够把它保存的记录根据键的排序（默认Comparable升序或者自己使用Comparable重新排序）可以用Iterator遍历Treemap。

??????? 当我们需要排序的映射时，建议使用TreeMap。

注意：在使用TreeMap时，key必须要实现Comparable接口，或者在构造TreeMap时传入Comparator,否则会在运行中抛出ClassCastException。

后续的ConcurrentHashMap，HashTableLinkHashMap在提到了再深入了解。