HashMap小例

MyHashMap

package com.cskaoyan.hashmap;

   +   
import java.util.LinkedHashSet;
import java.util.Set;

/*
API:
    void put(K key, V value)//     
    V get(K key)//        
    void delete(K key)//  key
    boolean contains(K key) //      key
    void clear() //  map
    boolean isEmpty() //      
    int size() //map  
    Set keys() //    key   
 */
public class MyHashMap {
    private static final int DEFAULT_CAPACITY = 16;//      0 100000000000000  2 30  
    private static final int MAX_CAPACITY = 1 << 30;//    ， 2      (     )
    private static final double DEFAULT_LOAD_FACTOR = 0.75;//    ，     。     
    
    //   
    private Entry[] table;
    //        ，    table           entry  ，  entry        hash ，        。
    private int size; //  
    private double loadFactor; //    ，   0.75
    private int threshold; //   ，          
    /**
    *      Entry? 
    *    1.  HashMap  ，HashMap         。        ， HashMap           *    0(1),           0(1)      。  
    *    2.hash    hash         ，       。（    ）
    *    3.      this            。
    */
    private static class Entry {
        K key;
        V val;
        int hash;
        Entry next;

        Entry(K key, V val, int hash) {
            this.key = key;
            this.val = val;
            this.hash = hash;
        }

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

    //     
    public MyHashMap() {
        this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    @SuppressWarnings("unchecked")
    public MyHashMap(int initialCapacity, double loadFactor) {
        // initialCapacity:           
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("initialCapacity=" + initialCapacity);
        }
        if (loadFactor <= 0) {
            throw new IllegalArgumentException("loadFactor=" + loadFactor);
        }
        this.loadFactor = loadFactor;
        int cap = (int) (initialCapacity / loadFactor);
        //       n   2   
        int n = tableLength(cap);
        table = new Entry[n];
        threshold = (int) (table.length * loadFactor);//            
    }

    //     cap    2^n (   ：    cap    2   )
    private int tableLength(int cap) {
        if (cap >= MAX_CAPACITY) return MAX_CAPACITY;
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n + 1;
    }

    /**
     *      ，  key  ，        
     *
     * @param key    
     * @param value  
     * @return   key   ,   null,   key  ，      
     */
    public V put(K key, V value) {
        if (key == null || value == null) {
            throw new IllegalArgumentException("Key or value can not be null");
        }
        int hash = hash(key);
        int idx = indexFor(hash, table.length);
        //     
        for (Entry e = table[idx]; e != null; e = e.next) {
            if (hash == e.hash && ((key == e.key) || key.equals(e.key))) {
                // key  
                V oldValue = e.val;
                e.val = value;
                return oldValue;
            }
        }
        
        // key   ,          。
        addEntry(key, value, hash, idx);
        return null;
    }

    private void addEntry(K key, V value, int hash, int idx) {
        //           
        if (size == threshold) {
            if (table.length == MAX_CAPACITY) {
                //        
                threshold = Integer.MAX_VALUE;
            } else {
                grow(table.length << 1); //    
                idx = indexFor(hash, table.length);
            }
        }
        //      
        Entry entryToAdd = new Entry<>(key, value, hash);
        entryToAdd.next = table[idx];//     
        table[idx] = entryToAdd;
        size++;
    }

    @SuppressWarnings("unchecked")
    private void grow(int newCapacity) {
        Entry[] newTable = new Entry[newCapacity];
        //  table      
        for (Entry e : table) {
            while (e != null) {
                Entry next = e.next;
                int idx = indexFor(e.hash, newCapacity);
                e.next = newTable[idx];
                newTable[idx] = e;
                e = next;
            }
        }
        table = newTable;//          table
        threshold = (int) (table.length * loadFactor);
    }

    private int hash(K key) {
        int h = key.hashCode();
        return (h >> 16) ^ (h << 16);
    }

    private int indexFor(int hash, int length) {
        return hash & (length - 1);(   2)
    }

    /**
     *   key   
     *
     * @param key    key
     * @return     ,   key     null
     */
    public V get(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null.");
        }   jdk   null   null      ？       ？
        int hash = hash(key);
        int idx = indexFor(hash, table.length);
        for (Entry e = table[idx]; e != null; e = e.next) {
            if (hash == e.hash && ((key == e.key) || (key.equals(e.key)))) {
                return e.val;
            }
        }
        return null;？？？   JDK
    }

    /**
     *      key,      
     *
     * @param key    key
     * @return key   value,   key     null
     */
    public V delete(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null.");
        }
        int hash = hash(key);
        int idx = indexFor(hash, table.length);
        Entry prev = null;//        
        for (Entry e = table[idx]; e != null; e = e.next) {
            if (hash == e.hash && ((key == e.key) || (key.equals(e.key)))) {
                V deleteValue = e.val;
                if (prev == null) table[idx] = e.next; // //      
                else prev.next = e.next;
                size--;
                return deleteValue;
            }
            prev = e;
        }
        return null;
    }

    /**
     *               
     *
     * @param key     
     * @return       true,     false
     */
    public boolean contains(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key cannot be null.");
        }
        int hash = hash(key);
        int idx = indexFor(hash, table.length);
        for (Entry e = table[idx]; e != null; e = e.next) {
            if (hash == e.hash && ((key == e.key) || (key.equals(e.key)))) {
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

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

    public void clear() {
        ///foreach???             ，   
        for(int i = 0; i < table.length; i++) {
            table[i] = null;
        }
        size = 0;
    }

    /**
     *           
     *
     * @return         
     */
    public Set keys() {
        Set set = new LinkedHashSet<>();
        for (Entry e : table) {
            while (e != null) {
                set.add(e.key);
                e = e.next;
            }
        }
        return set;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        for (Entry e : table) {
            while (e != null) {
                sb.append(e).append(", ");
                e = e.next;
            }
        }
        if (!isEmpty()) sb.delete(sb.length() - 2, sb.length());
        return sb.append("}").toString();
    }

    public static void main(String[] args) {
        MyHashMap map = new MyHashMap<>();
        /*System.out.println(map);
        System.out.println(map.size());
        System.out.println(map.isEmpty());*/

        map.put("   ", "  ");
        map.put("   ", "   ");
        map.put("  ", "   ");
        map.put("   ", "   ");

       /* System.out.println(map);
        System.out.println(map.size());
        System.out.println(map.isEmpty());*/

        /*System.out.println(map.put("   ", "  "));
        System.out.println(map);
        System.out.println(map.put("   ", "   "));
        System.out.println(map);*/
        // System.out.println(map.put(null, "A"));
        // System.out.println(map.put("A", null));

        // V get(K key)
        // System.out.println(map.get(null));
        /*System.out.println(map.get("   "));
        System.out.println(map.get("  "));*/

        // V delete(K key)
        // System.out.println(map.delete(null));
        /*System.out.println(map.delete("   "));
        System.out.println(map);
        System.out.println(map.size());*/

        /*System.out.println(map.delete("  "));
        System.out.println(map);
        System.out.println(map.size());*/

        // contains(K key)
        // System.out.println(map.contains(null));
        /*System.out.println(map.contains("  "));
        System.out.println(map.contains("  "));*/

        System.out.println(map.keys());
        map.clear();
        System.out.println(map.keys());
        System.out.println(map.size());
    }
}

添付ファイル1:capより大きい最小2のサブべき乗を計算する
|(または演算):1結果があれば1,0|0=0
&(演算):同時に1の結果が1である、そうでない場合は0.
^(排他演算子):0^0=0,0^1=1,1^0=1,1^1=0(同じ0で異なる場合は1)
例えば、cap=100であれば、n=99である.バイナリ変換:0000 0000 0110 0011、第1ステップ:n|=n>>1、
まずnを1ビット:0000 0000 0011 0001に右シフトし、|演算を行う.
0000 0000 0110 0011
0000 0000 0011 0001
0000 0000 0111 0011
次の手順に従います.
0000 0000 0111 0011
0000 0000 0001 1100
0000 0000 0111 1111
ステップ3:
0000 0000 0111 1111
0000 0000 0000 0111
0000 0000 0111 1111
ループダウン:0000 0000,0111,1111=127を得る
127+1 = 128;
したがって、100より大きい最小の2乗は128である
添付2:hash & (length -1)例えばhash=100;length -1 = 63;(8桁下しか書いていません)
hash = 0110 0100
length -1 = 0011 1111
​ = 0010 0100 (36)
したがってhashが100の値はインデックス36に存在するはずである.