import java.util.HashMap;
import java.util.Map;

public class App {

   public static void main(String[] args) {
       Map<String,String> map = new HashMap<>();
       map.put("劉一","劉一");
       map.put("陳二","陳二");
       map.put("張三","張三");
       map.put("李四","李四");
       map.put("王五","王五");
       map.put("Money","我是猴哥Money老師");
       System.out.println(map.get("Money"));
   }
}
//輸出結果：我是猴哥Money老師

    //數(shù)組：采用一段連續(xù)的存儲單元來存儲數(shù)據(jù)的
    //數(shù)組的特點: 查詢時間復雜度:0(1) ,刪除,插入,時間負責度0(N),總結：查詢塊，插入慢
    public static void main(String [] args){
        //數(shù)組的定義：初始化長度為10，數(shù)據(jù)類型Integer ,
        Integer integer[] = new Integer[10];
        //指定下標，復制
        integer[0]=0;
        //指定下標，復制
        integer[1]=1;
        //指定下標，復制
        integer[9]=2;
        //指定下標，復制
        integer[9]=400;
        System.out.println(integer[9]);
    }
    // 輸出結果：400

   public boolean add(E var1) {
        this.ensureCapacityInternal(this.size + 1);
        this.elementData[this.size++] = var1;
        return true;
    }

package node;

import com.sun.org.apache.bcel.internal.generic.IMPDEP1;

public class Node {

    public Node next;
    private Object data;


    public Node(Object next) {
        this.data = next;
    }

    //鏈表：鏈表是一種物理存儲單元上非連續(xù)，非順序的存儲結構
    //特點: 插入，刪除時間復雜度0(1) 查找遍歷時間復雜度0(N) 總結：插入快,查詢慢
    public static void main(String[] args){
        Node head =new Node("monkey");
        head.next =new Node("張三");
        head.next.next =new Node("劉一");
        System.out.println(head.data);
        System.out.println(head.next.data);
        System.out.println(head.next.next.data);
    }
}
//輸出結果:
//monkey
//張三
//劉一

   public boolean add(E var1) {
        this.linkLast(var1);
        return true;
    }
    //看上面有一個linkLast,如下:

   void linkLast(E var1) {
        LinkedList.Node var2 = this.last;
        LinkedList.Node var3 = new LinkedList.Node(var2, var1, (LinkedList.Node)null);
        this.last = var3;
        if (var2 == null) {
            this.first = var3;
        } else {
            var2.next = var3;
        }

        ++this.size;
        ++this.modCount;
    }
    //看上面有一個Node,如下:
    private static class Node<E> {
        E item;
        LinkedList.Node<E> next;
        LinkedList.Node<E> prev;

        Node(LinkedList.Node<E> var1, E var2, LinkedList.Node<E> var3) {
            this.item = var2;
            this.next = var3;
            this.prev = var1;
        }
    }
	  //上面有一個next,有一個prev 
	  //這是一個雙向鏈表

public class AsciiCode {

    public static void main(String[] args) {
        char c [] ="lies".toCharArray();
        for (int i = 0; i < c.length; i++) {
            System.out.println((c[i])+":" +(int)c[i]);
        }
    }

}
//輸出結果：
//l:108
//i:105
//e:101
//s:115

public class App {

    public static void main(String[] args) {
       //Map<String,String> map = new HashMap<>();
        App map = new App();
        map.put("劉一","劉一");
        map.put("陳二","陳二");
        map.put("張三","張三");
        map.put("李四","李四");
        map.put("王五","王五");
        map.put("Money","我是猴哥Money老師");
        //System.out.println(map.get("Money"));
    }

public void put(String key,String value){
 System.out.printf("key:%s:::::::::::::::;::hash值:%s:::::::::::::::::::存儲位置:%s\r\n",key,key.hashCode(),Math.abs(key.hashCode() % 15));
    }
}
//輸出結果:
//    key:劉一:::::::::::::::;::hash值:671464:::::::::::::::::::存儲位置:4
//    key:陳二:::::::::::::::;::hash值:1212740:::::::::::::::::::存儲位置:5
//    key:張三:::::::::::::::;::hash值:774889:::::::::::::::::::存儲位置:4
//    key:李四:::::::::::::::;::hash值:842061:::::::::::::::::::存儲位置:6
//    key:王五:::::::::::::::;::hash值:937065:::::::::::::::::::存儲位置:0
//    key:Monkey:::::::::::::::;::hash值:-1984628749:::::::::::::::::::存儲位置:4

/**
 * 自己手動定義Map
 * @param <K>
 * @param <V>
 */
public interface Map<K,V> {

    V put(K k,V v);

    V get(K k);

    int size();

     interface  Entry<K,V>{
      K getKey();
      V getValue();
     }

}

import sun.management.snmp.jvmmib.JvmRTInputArgsTableMeta;

/**
 * 自己定義HashMap
 * @param <K>
 * @param <V>
 */
public class HashMap<K,V> implements Map<K,V>{

    //存儲元素對象
    private Entry<K,V> table[] = null;

    //擴容初始化
    int size =0;

    //初始化存儲元素對象大小
    public HashMap() {
        this.table = new Entry[16];
    }

    /**
     * 1.通過key hash 算法算出hash值,然后取模
     * 2.取模后就有對應的index 數(shù)組下標,然后存儲對象<Entry>
     * 3.判斷當前對象是否為空，如果空，直接存儲，
     * 4.如果不為空，我們就要用到next 鏈表
     * 5.返回當前這個節(jié)點
     * @param k
     * @param v
     * @return
     */
    @Override
    public V put(K k, V v) {
       int index = hash(k);
       Entry<K,V> entry = table[index];
       if(null ==entry){
           //劉一，陳二，李四，王五 就開始存在這個entry,每個entry 對象則存儲到了對應table 中
           table[index] = new Entry<>(k, v, index, null);
           size++;
       }else{
           //沖突了，張三，Monkey
           table[index] = new Entry<>(k, v, index, entry);
       }
        
        return table[index].getValue();
    }

    private int hash(K k) {
        //HashMap 底層用到的是移位的操作，性能高很多 >>,我們這里就直接取模
        int index =k.hashCode() % 16;
        //Math.abs(index);
        return index>0?index:-index;
    }

    /**
     * 1.通過 key 進行hash 運算，取模，找到數(shù)組對應的下標 index
     * 2.判斷當前對象是否為空,如果不為空
     * 3.判斷是否相等，如果不相等
     * 4.判斷next 是否為空，如果不為空，
     * 5.再判斷相等，知道相等為止，或者為空為止
     * 6.然后返回
     *
     *
     *
     * @param k
     * @return
     */
    @Override
    public V get(K k) {
        //如果沒有存儲數(shù)據(jù)那size 為0，也不用查了，直接返回null
        if(size ==0){
            return null;
        }
        int index = hash(k);
        Entry<K, V> entry = findValue(table[index], k);
        //通過index 找打這個對象
        return entry==null?null:entry.getValue();
    }

    /**
     *
     * @param entry
     * @param k 查詢劉一
     * @return
     */
    private Entry<K,V> findValue(Entry<K,V> entry,K k) {
        //存的可能是數(shù)值類型，也可能是字符串類型
        if (k.equals(entry.getKey()) || k == entry.getKey()) {
            return entry;
            //如果不相等，估計這個節(jié)點是個鏈表，判斷它next 數(shù)據(jù)是否匹配
        } else {
            if(entry.next !=null){
                //用到遞歸，在鏈表里面一直查詢這個k,值是否相等
                return findValue(entry.next,k);
            }
        }
        return null;
    }

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



    class Entry<K,V> implements Map.Entry<K,V>{

         //存四個值
        K k;
        V v;
        int hash;
        Entry<K,V> next;

        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }
    }

}

public class Test {

    public static void main(String[] args) {
        Map<String,String> map = new HashMap<>();
        map.put("Monkey","我是moneky老師");
        map.put("東山再起","東山再起是位好同學");
        System.out.println(map.get("Monkey"));
        System.out.println(map.get("東山再起"));
    }

//輸出結果:
//我是moneky老師
//東山再起是位好同學
}

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

public class Test {

    public static void main(String[] args) {
        Map<String,String> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put("Monkey"+i,"我是moneky老師"+i);
        }
        System.out.println(map);
    }
}

  static final int TREEIFY_THRESHOLD = 8;