Map映射结构

Map接口

public interface Map<K,V>{
    void put(K key,V value);
    V remove(K key);
    boolean contains(K key);
    V get(K key);
    void set(K key,V newValue);
    int getSize();
    boolean isEmpty();
}

LinkedListMap

public class LinkedListMap<K,V> implements Map<K,V>{
    
    private class Node{
        public K key;
        public V value;
        public Node next;

        public Node(K key,V value,Node next){
            this.key=key;
            this.value=value;
            this.next=next;
        }

        public Node(K key){
            this(key,null,null);
        }

        public Node(){
            this(null,null,null);
        }

        @Override
        public String toString(){
            return key.toString()+" : "+value.toString();
        }
    }

    private Node dummyNode;

    private int size;

    public LinkedListMap(){
        dummyNode=new Node();
        size=0;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public boolean isEmpty(){
        return size==0;
    }

    private Node getNode(K key){
        Node cur=dummyNode.next;
        while(cur!=null){
            if (cur.key.equals(key)) {
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }

    @Override
    public boolean contains(K key){
        return getNode(key)==null;
    }

    @Override
    public V get(K key){
        Node node=getNode(key);
        return node==null?null:node.value;
    }

    @Override
    public void put(K key,V value){
        Node node = getNode(key);
        if(node==null){
            dummyNode.next=new Node(key,value,dummyNode.next);
            size++;
        }else{
            node.value=value;
        }
    }

    @Override
    public void set(K key,V value){
        Node node = getNode(key);
        if(contains(key)){
            node.value=value;
        }else{
            throw new IllegalArgumentException(key +" doesn't exist!");
        }
    }

    @Override
    public V remove(K key){
        Node prev=dummyNode;
        while(prev.next!=null){
            if (prev.next.key.equals(key)) {
                break;
            }
            prev=prev.next;
        }
        if (prev.next==null) {
            //其实可以和上面一样抛一个异常
            return null;
        }
        Node deleNode=prev.next;
        prev.next=deleNode.next;
        deleNode.next=null;
        size--;
        return deleNode.value;
    }
}

BSTMap

public class BSTMap<K extends Comparable,V> implements Map<K,V>{

    private class Node{
        public K key;
        public V value;
        public Node left;
        public Node right;
        public Node(K key,V value){
            this.key=key;
            this.value=value;
            left=null;
            right=null;
        }
    }  

    public Node root;

    private int size;

    public BSTMap(){
        root=null;
        size=0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void put(K key,V value){
        root=put(root,key,value);
    }

    //add元素后返回新的根节点
    private Node put(Node node,K key,V value){
        if (node == null) {
            size++;
            return new Node(key,value);
        }
        if(key.compareTo(node.key) < 0){
            node.left=put(node.left, key,value);
        }else if (key.compareTo(node.key) > 0) {
            node.right=put(node.right, key,value);   
        }else{
            //相等的情况
            node.value=value;
        }
        return node;
    }

    private Node getNode(Node node,K key){
        if (node==null) {
            return null;
        }
        int temp=node.key.compareTo(key);
        if (temp==0) {
            return node;
        }
        if (temp>0) { //node.key > key
            return getNode(node.left,key);
        }
        return getNode(node.right,key);
    }

    public boolean contains(K key){
        return getNode(root,key)!=null;
    }

    public V get(K key){
        Node node=getNode(root,key);
        return node==null?null:node.value;
    }

    public void set(K key,V newValue){
        Node node=getNode(root,key);
        if (node!=null) {
            node.value=newValue;
            return;
        }
        throw new IllegalArgumentException(key+ " doesn't exist");
    }

    private Node getMin(Node root){
        if (root.left==null) {
            return root;
        }
        return getMin(root.left);
    }

    private Node deleteMin(Node node){
        if (node.left==null) {
            return node.right;
        }
        node.left=deleteMin(node.left);
        return node;
    }

    public V remove(K key){
        Node node=getNode(root,key);
        if (node==null) {
            return null;
        }
        root=remove(node,key);
        size--;
        return node.value;
    }

    public Node remove(Node root,K key){
        if (key.compareTo(root.key)>0) { //key > root
            root.right=remove(root.right,key);
        }else if (key.compareTo(root.key)<0) {
            root.left=remove(root.left,key);
        }else{
            if (root.left==null) {
                return root.right;
            }
            if (root.right==null) {
                return root.left;
            }
            Node deleNode=root;
            root=getMin(root.right);
            root.right=deleteMin(deleNode.right);
            root.left=deleNode.left;
        }
        return root;
    }
}

MapTest

public class MapTest{
    public static void main(String[] args) {
        Map<Integer,Integer> map=new BSTMap<>();
        map.put(1,2);
        map.put(2,2);
        map.put(3,2);
        map.put(4,2);
        map.put(5,2);
        map.put(6,2);
        map.put(7,2);
        map.put(8,2);
        map.put(9,32131);
        map.put(11,2);
        System.out.println(map.contains(13)); //false
        System.out.println(map.getSize()); //10
        System.out.println(map.get(9)); //32131
        map.remove(9);
        System.out.println(map.get(9)); //null
        System.out.println(map.getSize()); //10
        map.set(11,1234567);
        System.out.println(map.get(11)); //1234567
    }
}

HashMap

import java.util.TreeMap;

public class HashTable<K,V>{
    private TreeMap<K,V>[] hashtable;
    private int M;
    private int size;

    private static final int upperTol=10;
    private static final int lowerTol=2;
    private static final int initCapacity=7;

    public HashTable(int M){
        this.M=M;
        size=0;
        hashtable=new TreeMap[M];
        for (int i=0;i<M;i++) {
            hashtable[i]=new TreeMap<>();
        }
    }

    public HashTable(){
        this(initCapacity);
    }

    private int hash(K key){
        return key.hashCode() & 0x7fffffff %M;
    }

    private int getSize(){
        return size;
    }

    public void add(K key,V value){
        TreeMap<K,V> map=hashtable[hash(key)];
        if(map.containsKey(key)){
            map.put(key,value);
        }else{
            map.put(key,value);
            size++;
            //扩容
            // size/M >=upperTol
            if (size>=upperTol*M) {
                resize(2*M);
            }
        }
    }

    public V remove(K key){
        TreeMap<K,V> map=hashtable[hash(key)];
        V ret=null;
        if(map.containsKey(key)){
            ret=map.remove(key);
            size--;
            if (size<lowerTol*M && M/2 >= initCapacity) {
                resize(M/2);
            }
        }
        return ret;
    }

    public void resize(int size){
        TreeMap<K,V> newHashTable=new TreeMap[size];
        for (int i=0;i<size;i++) {
            newHashTable[i]=new TreeMap<>();
        }
        int oldSize=M;
        this.M=size; //要先将M设置好,不然hash的值不对
        for (int i=0;i<oldSize;i++) {
            TreeMap<K,V> map=hashtable[i];
            for (K key:map.keySet()) {
                newHashTable[hash(key)].put(key,map.get(key));
            }
        }
        this.hashtable=newHashTable;
    }

    public void set(K key,V value){
        TreeMap<K,V> map=hashtable[hash(key)];
        if(!map.containsKey(key)){
            throw new IllegalArgumentException("key not exist!");
        }
        map.put(key,value);
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }
}

源码地址

Github