[数据结构与算法]HashMap的数据结构

添加数据原理

1. HashMap底层是(数组+链表+红黑树)
2. 添加一个元素时，先得到hash值，然后把它转成索引值
3. 然后找到存储数据表table，看这个索引位置是否已经存放元素
4. 如果没有，直接加入
5. 如果有，调用equals方法对准备加入元素和已有元素进行比较，如果相同，则放弃添加，如果不相同，则添加至最后
6. 在Java8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD(默认为8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化

数据结构

1. table：存放数据类型为Node<hash,key,value,next>,存放基本数据
2. entrySet：存放数据类型为Entry<key,value>,存放了数据的引用
3. 同理，keySet和values也一样
4. keySet：可以单独存放了Node节点中key值的引用
5. values：可以单独存放Node节点中value值的引用

package aggregate.map;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapSource_ {
    public static void main(String[] args) {
        Map map = new HashMap();

        map.put("1","tom");
        map.put("2","jack");

        //1.k-v 最后是存放在HashMap$Node类型的Node节点中
        //2.为了方便遍历，还会创建EntrySet集合，该集合存放的数据类型为Entry，而Entry中又包含了k-v
        //  EntrySet<Entry<k-v>>
        //3.EntrySet中，定义的类型是Map.Entry，但是实际上存放的还是HashMap$Node
        //  这是因为HashMap$Node implements Map.Entry
        //4.当把HashMap$Node对象存放到EntrySet中，就方便了我们遍历
        //5.简而言之，EntrySet中存放的只是Node中数据的引用

        Set set = map.entrySet();
        System.out.println(set.getClass());
        for (Object obj : set) {
            //System.out.println(obj.getClass());
            //为了从HashMap$Node 取出k-v
            //1.先做一个向下转型
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "-" + entry.getValue());
        }

        //同理，keySet和values也一样
        //keySet可以单独存放了Node节点中key值的引用
        //values可以单独存放Node节点中value值的引用
        Set key = map.keySet();
        Collection value = map.values();
        System.out.println(key.getClass() + "\n" + value.getClass());
    }
}