Map接口总结与HashMap源码分析

Map接口总结与HashMap源码分析,第1张

Map接口

1.Map,用于保存K-V(双列元素)
2.Map中的Key Value可以是任意引用分类型的数据,会封装到HashMap的Node对象中
3.Map的key不允许重复。原因和HashSet一样。
4.Map中的value可以重复
5.Map的key可以为null,value也可以为null。
6.常用String类作为Map的key
7.key value一对一,通过指定的key可以得到value
8.Map存放数据的key-value示意图,一对k-v是放在HashMap$Node中的,因为Node实现了Entry接口,所以一对k-v就是一个Entry

就是说:
为了方便管理,遍历数据
把node封装成一个entry,再把entry放在entryset集合中,因为entry中有方法适合遍历
从entryset中取出数据,是node(因为node实现了entry),我们做个转型,把node型转化
为entry型。再调用方法

关于entryset总结
1. .k-v最后是存放在:
HashMap$Node node =newNode(hash, key, value, null);

2.k-v为了方便程序员的遍历,还会创建EntrySet集合,这个集合存放的数据元素类型是Entry,Entry对象就有k,v EntrySet>
3.
EntrySet中,定义的类型是Entry,但是实际上还是存放的Node。因为Node实现了Map.Entry

4.把node对象存放在entrySet中,为了方便我们遍历,因为Map.entry提供了重要的方法 k getkey() v getvalue();

Map map= new HashMap<>();
map.put("no1","汉顺");
map.put("no2","顺");
map.put("no1","张三");//替换old值
map.put("no3","张三");


//.k-v为了方便程序员的遍历,还会创建EntrySet集合,
// 这个集合存放的数据元素类型是Entry,Entry对象就有k,v
// EntrySet>
Set set = map.entrySet();
System.out.println(set.getClass());//HashMap$EntrySet


//获得EntrySet中的元素
//虽然定义的类型是Entry,但是实际上还是存放的Node
//因为Node实现了Map.Entry
for(Object obj : set)
{
    System.out.println(obj.getClass());//HashMap$Node
    //为了从HashMap$Node中取出k-v
    //先做转型
    //先转化为entry类型,这里面有方法取得k-v
    Map.Entry entry = (Map.Entry) obj;
    System.out.println(entry.getKey()+"-"+entry.getValue());
}

Map遍历方式

1.containsKey:查找键是不是存在
2.keySet:获得所有的键
3.entrySet:获得所有的关系k-v
4.values:获取所有的值

public class MapFor {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("邓超","孙丽");
        map.put("王宝强","马蓉");
        map.put("宋喆","马蓉");
        map.put("孙胜顺","刘秋丽");
        map.put(null,"刘亦菲");
        map.put(null,"刘令");
        map.put("鹿晗","关晓彤");


        //第一组
        //先取出所有的key
        Set keyset = map.keySet();
        //(1).增强for
        System.out.println("----第一种方式--");
        for(Object key: keyset){
            System.out.println(key+"-"+map.get(key));


        }
        //(2)迭代器
        Iterator iterator = keyset.iterator();
        System.out.println("----第一种方式迭代器--");
        while (iterator.hasNext()) {
            Object key =  iterator.next();
            System.out.println(key+"-"+map.get(key));


        }


        //第二组
        //把所有的values取出
        Collection values = map.values();
        //这里可以使用所有
        //(1)增强for
        System.out.println("----取出所有的values,增强for---");
        for(Object value:values){
            System.out.println(value);
        }


        //(2)迭代器
        System.out.println("----取出所有的values,迭代器---");
        Iterator iterator1 = values.iterator();
        while (iterator1.hasNext()) {
            Object value =  iterator1.next();
            System.out.println(value);
        }


        //第三组
        //通过EntrySet
        Set set = map.entrySet();
        System.out.println("------entryset的增强for---");
        //(1)增强for
        for(Object obj : set){
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey()+"-"+entry.getValue());
        }
        //(2)迭代器
        Iterator iterator2 = set.iterator();
        System.out.println("------entryset的增强迭代器---");
        while (iterator2.hasNext()) {
            Object next =  iterator2.next();//取出的是Node,Node实现了Map.entry
            Map.Entry entry = (Map.Entry)next;
            System.out.println(entry.getKey()+"-"+entry.getValue());
        }


    }
}

HashMap小结

HashMap底层机制和源码


小结
1.HashMap底层维护了Node类型的数组table,默认为null。
2.当创建对象时,将加载因子(loadfactor)初始化为0.75.
3.当添加key-value时,通过key的哈希值得到在table的索引。
然后判断该索引处是否有元素,如果没有元素直接添加。如果该索引处有元素,继续判断该元素的key和准备加入的ke y是不是相等。如果相等,则直接替换value;如果不相等需要判断是树结构还是链表结构,做出相应处理。如果添加时发现容量不够,则需要扩容。
4.第一次添加,扩容的容量为16,临界值为12
5.以后再扩容,则需要扩容table容量为原来的2倍,临界值为原来的2倍,即24,依次类推.
6.在Java8中,,如果一条链表的元素个数超过TREEIFY THRESHOLD(默认是8),并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)

HashMap源码分析
HashMap map = new HashMap<>();


map.put("java",10);
map.put("php",10);
map.put("java",20);
System.out.println(map);

1.执行构造器 new HashMap()
初始化加载因子,loadfactor = 0.75
HashMap$Node[] table = null;

2.执行put方法
会调用hash(key)计算key的哈希值
k=“java” value =10

hash(key) :得到哈希值
算法如下:

3.执行putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node[] tab; Node p; int n, i;

    //第一次put执行到这里的时候,table==null
    if ((tab = table) == null || (n = tab.length) == 0)

        //table为null,进入resize()方法,给table申请16个空间大小
  n=16
        n = (tab = resize()).length;

    //根据hash值,计算索引位置,如果这个位置没有元素,直接挂上去
    //(第二次执行put方法的时候,table不为null,就直接进入这里)(不超过12次都是直接进入这里)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    else {
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    //看table中元素的个数是否到达12,如果到达就扩容
    if (++size > threshold)
        resize();

    afterNodeInsertion(evict);
    return null;
}

执行resize()方法的时候,
newCap=16 newThr=12;
Node[] newTab = new Node[16];
return newTable



自己总结:
执行构造方法,获得加载因子0.75
进入put方法,里面有pubVal方法,putval方法的第一个参数是一个hash(key)方法
进去发现,根据key得到hash值。
(第一次put的时候会进行下面两步,从第二次开始只要不超过12次,直接跳过)
进去putval,判断table==null就进入resize方法扩容。
进去resize,定义了两个变量A=16 B=12, new了一个含有16个空间大小的数组newNode,返回这个数组,所以table=16个空间大小了
再在putval方法里,根据hash值,计算索引位置,发现索引位置上没有元素,直接插入。
(如果索引上有元素,进入下面三种情况)
判断 table中元素的大小是不是>12,如果大于,就进入resize方法扩容

else {
        Node e; K k;
        //put("java",20)的时候
               //满足这个条件
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        //如果是个红黑树了,就按照红黑树的方式处理
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
  
        //如果找到的位置,后面是链表,就循环比较
        else {
            for (int binCount = 0; ; ++binCount) {
                
                             //如果循环到了最后一个元素
                if ((e = p.next) == null) {

                    //直接插入到最后一个位置
                    p.next = newNode(hash, key, value, null);

                    //如果到了8个,就变成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        
                        treeifyBin(tab, hash);
                    break;
                }

                //如果中间有相同的,直接退出循环,到下面直接替换
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //满足
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                //直接替换
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/729604.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-27
下一篇 2022-04-27

发表评论

登录后才能评论

评论列表(0条)

保存