首页 > 其他分享 >一篇文章让你面试畅谈HashMap,Hashtable,TreeSet,TreeMap

一篇文章让你面试畅谈HashMap,Hashtable,TreeSet,TreeMap

时间:2023-04-16 10:08:21浏览次数:42  
标签:map TreeMap value Hashtable key Entry null out TreeSet


HashMap

  • Map与Collection并列存在。用于保存具有映射关系的数据:Key-Value
  • Map中的key和value可以是任何引用类型,会封装到HashMap$Node对象中
  • Map中的key不允许重复,原因和HashSet一样,前面分析过源码
  • Map中的value可以重复
  • Map的key可以是null,value也可以为null,注意key为null只能有一个,value为null可以多个
  • 常用String类作为Map的key
  • key和value之间存在单向一对一关系,即通过指定的key总能找到对应的value
  • 和HashSet一样,不保证映射的顺序,因为底层是以hash表的方式来存储
  • HashMap没有实现同步,因此是线程不安全的,方法没有做同步互斥的操作,没有synchronized
    Map接口的特点:
    Map存放数据的key-value示意图,一对k-v是放在HashMap$Node的,又因为Node实现了Entry接口,有些书也说一对k-v就是一个Entry。
    k-v最后是
HashMap$Node node = newNode(hash, key, value, null);

k-v为了方便程序员的遍历,还会创建EntrySet集合,该集合存放的元素的类型Entry,而一个Entry对象就有k,v,EntrySet<Entry
<K,V>>

transient Set<Map.Entry<K,V>> entrySet;

entrySet中,定义的类型是Map.Entry,但是实际上存放的还是HashMap$Node,这是因为

static class Node<K,V> implements Map.Entry<K,V>

当把HashMap$Node对象存放到entrySet就方便我们的遍历,因为Map.Entry提供了重要方法

public final K getKey() 
 public final V getValue()

一篇文章让你面试畅谈HashMap,Hashtable,TreeSet,TreeMap_java


Map的六大遍历方式:

package map;

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

public class HashMapDemo {

    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<String, String>();
        // 键不能重复,值可以重复
        map.put("san", "张三");
        map.put("si", "李四");
        map.put("wu", "王五");
        map.put("wang", "老王");
        map.put("wang", "老王2");// 老王被覆盖
        map.put("lao", "老王");
        System.out.println("-------直接输出hashmap:-------");
        System.out.println(map);
        /**
         * 遍历HashMap
         */
        // 1.获取Map中的所有键
        System.out.println("-------foreach获取Map中所有的键:------");
        Set<String> keys = map.keySet();
        for (String key : keys) {
            System.out.print(key+"  ");
        }
        System.out.println();//换行
        // 2.获取Map中所有值
        System.out.println("-------foreach获取Map中所有的值:------");
        Collection<String> values = map.values();
        for (String value : values) {
            System.out.print(value+"  ");
        }
        System.out.println();//换行
        // 3.得到key的值的同时得到key所对应的值
        System.out.println("-------得到key的值的同时得到key所对应的值:-------");
        Set<String> keys2 = map.keySet();
        for (String key : keys2) {
            System.out.print(key + ":" + map.get(key)+"   ");

        }
        /**
         * 如果既要遍历key又要value,那么建议这种方式,因为如果先获取keySet然后再执行map.get(key),map内部会执行两次遍历。
         * 一次是在获取keySet的时候,一次是在遍历所有key的时候。
         */
        // 当我调用put(key,value)方法的时候,首先会把key和value封装到
        // Entry这个静态内部类对象中,把Entry对象再添加到数组中,所以我们想获取
        // map中的所有键值对,我们只要获取数组中的所有Entry对象,接下来
        // 调用Entry对象中的getKey()和getValue()方法就能获取键值对了
        Set<java.util.Map.Entry<String, String>> entrys = map.entrySet();
        for (java.util.Map.Entry<String, String> entry : entrys) {
            System.out.println(entry.getKey() + "--" + entry.getValue());
        }

        /**
         * HashMap其他常用方法
         */
        System.out.println("after map.size():"+map.size());
        System.out.println("after map.isEmpty():"+map.isEmpty());
        System.out.println(map.remove("san"));
        System.out.println("after map.remove():"+map);
        System.out.println("after map.get(si):"+map.get("si"));
        System.out.println("after map.containsKey(si):"+map.containsKey("si"));
        System.out.println("after containsValue(李四):"+map.containsValue("李四"));
        System.out.println(map.replace("si", "李四2"));
        System.out.println("after map.replace(si, 李四2):"+map);
    }

}

源码分析:

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

Hashtable

  • 存放的元素时键值对:即 K-V
  • hashtable的键和值都不能为null,否则会抛出空指针异常
  • hashTable使用方法基本上和HashMap一样
  • hashTable是线程安全的,hashMap是线程不安全的
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable
public synchronized V put(K key, V value)

底层有数组 Hashtable $ Entry[] 初始化为11

private static class Entry<K,V> implements Map.Entry<K,V>

threshold 8 = 11 * 0.75

分析扩容源码:

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
//添加K-V 封装到Entry
        addEntry(hash, key, value, index);
        return null;
    }
private void addEntry(int hash, K key, V value, int index) {
        modCount++;

        Entry<?,?> tab[] = table;
        
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            //扩容
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
    }
protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        //关键点:新的容量 11 * 2 + 1 = 23
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
    }

HashMap与Hashtable的对比:

一篇文章让你面试畅谈HashMap,Hashtable,TreeSet,TreeMap_jvm_02

Properties

  • 继承自Hashtable类并且实现了Map接口,也是使用键值对的形式来保存数据
  • 使用特定和Hashtable类似
  • 还可用于从 xxx.properties 文件通常作为配置文件,这个知识点在IO流举例

TreeSet

当我们使用无参构造器创建TreeSet时,仍然时无序的
老师希望添加的元素按照字符串大小来排序
使用TreeSet提供的一个构造器,可以传入一个比较器

new TreeSet<>(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).compareTo((String) o2);
            }
        });

构造器把传入的比较器对象,赋给了TreeSet的底层的TreeMap的属性this.comparator

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
Comparator<? super K> cpr = comparator;
        if (cpr != null) {//cpr就是我们的匿名内部类
            do {
                parent = t;
                //匿名内部类方法
                cmp = cpr.compare(key, t.key);//动态绑定我们的匿名内部类(对象)
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else//如果相等,即返回0,这个key就加入不了
                    return t.setValue(value);
            } while (t != null);

按长度排从小到大排

new TreeSet<>(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                return ((String)o1).length() - ((String) o2).length();
            }
        });

TreeMap

一篇文章让你面试畅谈HashMap,Hashtable,TreeSet,TreeMap_jvm_03

调用put方法,第一次添加,把k-v封装到Entry对象,放入root

Entry<K,V> t = root;
        if (t == null) {
        //检查是不是null,并给比较器赋一个自己重写的比较器
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }

第二次以及以上次数提交

Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            do {//遍历所有的key,给当前key找到适当位置
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else//如果遍历过程中,发现准备添加Key和当前已有的Key相等就不添加
                    return t.setValue(value);
            } while (t != null);
        }


标签:map,TreeMap,value,Hashtable,key,Entry,null,out,TreeSet
From: https://blog.51cto.com/u_15911055/6193297

相关文章

  • TreeMap源码
          常见面试题:    ......
  • 为什么HashMap的key允许空值,而Hashtable却不允许
    结论:HashMap对象的key、value值均可为null。      Hashtable对象的key、value值均不可为null。且两者的的key值均不能重复,若添加key相同的键值对,后面的value会自动覆盖前面的value,但不会报错。1.从源码分析HashMap从源码分析:  HashMap在put的时候会调用hash()......
  • TreeMap
        ......
  • TreeMap运行错误
    Exceptioninthread"main"java.lang.ClassCastException:Day16_TreeMap.Starcannotbecasttojava.lang.Comparable提示类型转换错误,publicstaticvoidmain(String[]args){TreeMap<Star,String>Tr=newTreeMap<Star,String>();//下句出错......
  • TreeMap特性
    TreeMap可以实现的数据结构具有平衡搜索二叉树的设计:AVL,SB树,红黑树常规外设计:跳表时间复杂度都是:Log(N)区别只有常数级别的TreeMap<Integer,String>treeMap......
  • HashTable源码分析
    HashTable是一个线程安全的HashMap,是jdk早期版本的产物,但其效率较低1.初始化可以看到,与HashMap不同,HashTable无参构造是默认会构造一个容量为11的数组,而HashMap在无参......
  • Hashtable 键值对集合
    usingSystem;usingSystem.Collections;namespaceHashtable_键值对集合{classProgram{staticvoidMain(string[]args){......
  • Treemap按key和value降序排序
    Treemap是一种根据键排序的数据结构,可以通过重载它的比较器来按照值排序。要按键排序,可以使用默认的比较器,而要按值排序,可以创建一个自定义的比较器并将其传递给treemap的......
  • TreeMap
    TreeMap是有序map,通过key进行排序1.TreeMap是如何实现去重和排序的?TreeMap实现了SortedMap接口,它是一个key有序的Map类。TreeMap的默认排序规则:根据key元素的compareTo......
  • C++中的HashTable性能优化
    C++中的HashTable性能优化-知乎https://zhuanlan.zhihu.com/p/614105687C++中的HashTable性能优化腾讯技术工程​编程话题下的优秀答主​关注 72......