面试半年！三面阿里，四面蚂蚁金服，居然倒在了一个Java集合之Map上？

2021-04-22 00:31

阅读：388

标签：错误存放位置 data- 字符串 time nod stat 技术 ges

Map接口

Map与Collection并列存在。用于保存具有映射关系的数据:key-value
Map中的key和value都可以是任何引用类型的数据
Map中的key用set来存放，不允许重复，即同一个Map对象所对应的类，须重写 hashCode()和 equals()方法
常用 String类作为Map的“键”
key和value之间存在单向一对一关系，即通过指定的key总能找到唯一的、确定的value
Map接口的常用实现类:HashMap、TreeMap、LinkedHashMap和Properties。其中，HashMap是Map接口使用频率最高的实现类

1. 常见实现类结构

|----Map:双列数据，存储key-value对的数据   ---类似于高中的函数：y = f(x)
     |----HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value
          |----LinkedHashMap:保证在遍历map元素时，可以照添加的顺序实现遍历。
                    原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
                    对于频繁的遍历操作，此类执行效率高于HashMap。
     |----TreeMap:保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
                      底层使用红黑树
     |----Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
          |----Properties:常用来处理配置文件。key和value都是String类型
 
 
HashMap的底层： 数组+链表  （JDK 7.0及之前)
               数组+链表+红黑树 （JDK 8.0以后)

1.1 HashMap

HashMap是Map接口使用频率最高的实现类。

允许使用null键和null值，与 HashSet一样，不保证映射的顺序。

所有的key构成的集合是set：无序的、不可重复的。所以，key所在的类要重写equals()和 hashCode()

所有的value构成的集合是Collection：无序的、可以重复的。所以，value所在的类要重写:equals()

一个key-value构成一个entry

所有的entry构成的集合是Set：无序的、不可重复的

HashMap判断两个key相等的标准是：两个key通过equals()方法返回true，hashCode值也相等。

HashMap判断两个value相等的标准是：两个value通过equals()方法返回true.

代码示例：

@Test
public void test1(){
    Map map = new HashMap();
 
    map.put(null,123);
 
}

1.2 LinkedHashMap

LinkedHashMap底层使用的结构与HashMap相同，因为LinkedHashMap继承于HashMap.
区别就在于：LinkedHashMap内部提供了Entry，替换HashMap中的Node.
与Linkedhash Set类似，LinkedHashMap可以维护Map的迭代顺序：迭代顺序与Key-value对的插入顺序一致
代码示例：

@Test
public void test2(){
    Map map = new LinkedHashMap();
    map.put(123,"AA");
    map.put(345,"BB");
    map.put(12,"CC");
 
    System.out.println(map);
}

1.3 TreeMap

TreeMap存储Key-Value对时，需要根据key-value对进行排序。TreeMap可以保证所有的 Key-Value对处于有序状态。

TreeSet底层使用红黑树结构存储数据

TreeMap的Key的排序:

自然排序： TreeMap的所有的Key必须实现Comparable接口，而且所有的Key应该是同一个类的对象，否则将会抛出ClasssCastEXception()
定制排序：创建 TreeMap时，传入一个 Comparator对象，该对象负责对TreeMap中的所有key进行排序。此时不需要Map的Key实现Comparable接口
TreeMap判断两个key相等的标准：两个key通过 compareTo()方法或者compare()方法返回0.

1.4 Hashtable

Hashtable是个古老的Map实现类，JDK1.0就提供了。不同于 HashMap，Hashtable是线程安全的.

Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用

与HashMap.不同，Hashtable不允许使用null作为key和value.

与HashMap一样，Hashtable也不能保证其中Key-value对的顺序.

Hashtable判断两个key相等、两个value相等的标准，与HashMap-致.

1.5 Properties

Properties类是Hashtable的子类，该对象用于处理属性文件

由于属性文件里的key、value都是字符串类型，所以Properties里的key和value都是字符串类型

存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法

代码示例：

//Properties:常用来处理配置文件。key和value都是String类型
public static void main(String[] args)  {
    FileInputStream fis = null;
    try {
        Properties pros = new Properties();
 
        fis = new FileInputStream("jdbc.properties");
        pros.load(fis);//加载流对应的文件
 
        String name = pros.getProperty("name");
        String password = pros.getProperty("password");
 
        System.out.println("name = " + name + ", password = " + password);
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        if(fis != null){
            try {
                fis.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
 
        }
    }
 
}

2. 存储结构的理解：

Map中的key:无序的、不可重复的，使用Set存储所的key ---> key所在的类要重写equals()和hashCode() （以HashMap为例)
Map中的value:无序的、可重复的，使用Collection存储所的value --->value所在的类要重写equals()
一个键值对：key-value构成了一个Entry对象。
Map中的entry:无序的、不可重复的，使用Set存储所的entry

3. 常用方法

3.1添加、删除、修改操作：

Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key)：移除指定key的key-value对，并返回value
void clear()：清空当前map中的所有数据
代码示例：

@Test
public void test1() {
    Map map = new HashMap();
    //Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
    map.put("AA",123);
    map.put("ZZ",251);
    map.put("CC",110);
    map.put("RR",124);
    map.put("FF",662);
    System.out.println(map);//{AA=123, ZZ=251, CC=110, RR=124, FF=662}
 
    //Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
    map.put("ZZ",261);
    System.out.println(map);//{AA=123, ZZ=261, CC=110, RR=124, FF=662}
 
    //void putAll(Map m):将m中的所有key-value对存放到当前map中
    HashMap map1 = new HashMap();
    map1.put("GG",435);
    map1.put("DD",156);
    map.putAll(map1);
    System.out.println(map);//{AA=123, ZZ=261, CC=110, RR=124, FF=662, GG=435, DD=156}
 
    //Object remove(Object key)：移除指定key的key-value对，并返回value
    Object value = map.remove("GG");
    System.out.println(value);//435
    System.out.println(map);//{AA=123, ZZ=261, CC=110, RR=124, FF=662, DD=156}
 
    //void clear()：清空当前map中的所有数据
    map.clear();
    System.out.println(map.size());//0  与map = null操作不同
    System.out.println(map);//{}
}

3.2元素查询的操作：

Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等
代码示例：

@Test
public void test2() {
    Map map = new HashMap();
    map.put("AA", 123);
    map.put("ZZ", 251);
    map.put("CC", 110);
    map.put("RR", 124);
    map.put("FF", 662);
    System.out.println(map);//{AA=123, ZZ=251, CC=110, RR=124, FF=662}
    //Object get(Object key)：获取指定key对应的value
    System.out.println(map.get("AA"));//123
 
    //boolean containsKey(Object key)：是否包含指定的key
    System.out.println(map.containsKey("ZZ"));//true
 
    //boolean containsValue(Object value)：是否包含指定的value
    System.out.println(map.containsValue(123));//true
 
    //int size()：返回map中key-value对的个数
    System.out.println(map.size());//5
 
    //boolean isEmpty()：判断当前map是否为空
    System.out.println(map.isEmpty());//false
 
    //boolean equals(Object obj)：判断当前map和参数对象obj是否相等
    Map map1 = new HashMap();
    map1.put("AA", 123);
    map1.put("ZZ", 251);
    map1.put("CC", 110);
    map1.put("RR", 124);
    map1.put("FF", 662);
    System.out.println(map.equals(map1));//true
}

3.3 元视图操作的方法：

Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value对构成的Set集合
代码示例：

@Test
public void test3() {
    Map map = new HashMap();
    map.put("AA", 123);
    map.put("ZZ", 251);
    map.put("CC", 110);
    map.put("RR", 124);
    map.put("FF", 662);
    System.out.println(map);//{AA=123, ZZ=251, CC=110, RR=124, FF=662}
    //遍历所有的key集:Set keySet()：返回所有key构成的Set集合
    Set set = map.keySet();
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
    System.out.println("--------------");
    //遍历所有的value集：Collection values()：返回所有value构成的Collection集合
    Collection values = map.values();
    for (Object obj :
         values) {
        System.out.println(obj);
    }
    System.out.println("---------------");
    //Set entrySet()：返回所有key-value对构成的Set集合
    Set entrySet = map.entrySet();
    Iterator iterator1 = entrySet.iterator();
    //方式一：
    while (iterator1.hasNext()) {
        Object obj = iterator1.next();
        //entrySet集合中的元素都是entry
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "-->" + entry.getValue());
    }
    System.out.println("--------------");
 
    //方式二：
    Set keySet = map.keySet();
    Iterator iterator2 = keySet.iterator();
    while (iterator2.hasNext()) {
        Object key = iterator2.next();
        Object value = map.get(key);
        System.out.println(key + "==" + value);
    }
}

总结：常用方法：

添加：put(Object key,Object value)
删除：remove(Object key)
修改：put(Object key,Object value)
查询：get(Object key)
长度：size()
遍历：keySet() / values() / entrySet()

4. 内存结构说明：（难点）

4.1 HashMap在JDK 7.0中实现原理：

4.1.1 HashMap的存储结构：

JDK 7.0及以前的版本：HashMap是数组+链表结构（地址链表法）

JDK 8.0版本以后：HashMap是数组+链表+红黑树实现

4.1.2 对象创建和添加过程：

HashMap map = new HashMap():

在实例化以后，底层创建了长度是16的一维数组Entry[] table。

? ...可能已经执行过多次put...

map.put(key1,value1):

首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
如果此位置上的数据为空，此时的key1-value1添加成功。 ----情况1
如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值：
如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。----情况2
如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：
如果equals()返回false:此时key1-value1添加成功。----情况3
如果equals()返回true:使用value1替换value2。

补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。

在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

4.1.3 HashMap的扩容

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对 HashMap的数组进行扩容，而在HashMap数组扩容之后，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是 resize。

4.1.4 HashMap扩容时机

当HashMap中的元素个数超过数组大小（数组总大小 length，不是数组中个数）* loadFactor时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_ FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT INITIAL CAPACITY)为16，那么当 HashMap中元素个数超过16 * 0.75=12（这个值就是代码中的 threshold值，也叫做临界值）的时候，就把数组的大小扩展为2 * 16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

4.2 HashMap在JDK 8.0底层实现原理：

4.2.1 HashMap的存储结构：

HashMap的内部存储结构其实是数组+链表+红黑树的组合。

4.2.2 HashMap添加元素的过程：

当实例化一个HashMap时，会初始化 initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为 initialCapacity的Node数组，这个长度在哈希表中被称为容量（Capacity），在这个数组中可以存放元素的位置我们称之为“桶”（ bucket），每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。

每个 bucket中存储一个元素，即一个Node对象，但每一个Noe对象可以带个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个 TreeNode对象，每一个Tree node对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。

4.2.3 HashMap的扩容机制:

当HashMapl中的其中一个链的对象个数没有达到8个和JDK 7.0以前的扩容方式一样。
当HashMapl中的其中一个链的对象个数如果达到了8个，此时如果 capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成 Tree Node类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。

4.2.4 JDK 8.0与JDK 7.0中HashMap底层的变化：

new HashMap():底层没有创建一个长度为16的数组

JDK 8.0底层的数组是：Node[],而非Entry[]

首次调用put()方法时，底层创建长度为16的数组

JDK 7.0底层结构只有：数组+链表。JDK 8.0中底层结构：数组+链表+红黑树。

形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所数据改为使用红黑树存储。

4.3 HashMap底层典型属性的属性的说明：

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threshold：扩容的临界值，= 容量*填充因子：16 * 0.75 => 12
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:JDK 8.0引入
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:64

4.4 LinkedHashMap的底层实现原理

static class Node implements Map.Entry{
    final int hash;
    final K key;
    V value;
    Node next;
}

LinkedHashM中内部类Entry源码：

static class Entry extends HashMap.Node {
    Entry before, after;//能够记录添加的元素的先后顺序
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

5. TreeMap的使用

向TreeMap中添加key-value，要求key必须是由同一个类创建的对象要照key进行排序：自然排序、定制排序

代码示例：

//自然排序
@Test
public void test() {
    TreeMap map = new TreeMap();
    User u1 = new User("Tom", 23);
    User u2 = new User("Jarry", 18);
    User u3 = new User("Bruce", 56);
    User u4 = new User("Davie", 23);
 
    map.put(u1, 98);
    map.put(u2, 16);
    map.put(u3, 92);
    map.put(u4, 100);
 
    Set entrySet = map.entrySet();
    Iterator iterator = entrySet.iterator();
    while (iterator.hasNext()) {
        Object obj = iterator.next();
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}
 
//定制排序：按照年龄大小排
@Test
public void test2() {
    TreeMap map = new TreeMap(new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            if (o1 instanceof User && o2 instanceof User) {
                User u1 = (User) o1;
                User u2 = (User) o2;
                return Integer.compare(u1.getAge(), u2.getAge());
            }
            throw new RuntimeException("输入数据类型错误");
        }
    });
    User u1 = new User("Tom", 23);
    User u2 = new User("Jarry", 18);
    User u3 = new User("Bruce", 56);
    User u4 = new User("Davie", 23);
 
    map.put(u1, 98);
    map.put(u2, 16);
    map.put(u3, 92);
    map.put(u4, 100);
 
    Set entrySet = map.entrySet();
    Iterator iterator = entrySet.iterator();
    while (iterator.hasNext()) {
        Object obj = iterator.next();
        Map.Entry entry = (Map.Entry) obj;
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}

6.使用Properties读取配置文件

代码示例：

//Properties:常用来处理配置文件。key和value都是String类型
public static void main(String[] args)  {
    FileInputStream fis = null;
    try {
        Properties pros = new Properties();
 
        fis = new FileInputStream("jdbc.properties");
        pros.load(fis);//加载流对应的文件
 
        String name = pros.getProperty("name");
        String password = pros.getProperty("password");
 
        System.out.println("name = " + name + ", password = " + password);
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        if(fis != null){
            try {
                fis.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
 
        }
    }
 
}

最后

大家看完有什么不懂的话可以在下方留言评论，也可以私信问我，我一般看到之后都会回复的。也欢迎大家关注我的公众号：前程有光，马上金九银十跳槽面试季，整理了1000多道将近500多页pdf文档的Java面试题资料，文章都会在里面更新，整理的资料也会放在里面。

面试半年！三面阿里，四面蚂蚁金服，居然倒在了一个Java集合之Map上？

标签：错误存放位置 data- 字符串 time nod stat 技术 ges

原文地址：https://www.cnblogs.com/lwh1019/p/13278903.html

上一篇：Web前端和JAVA应该学哪个？哪个就业形势更好？

下一篇：C++ const和constexpr

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：面试半年！三面阿里，四面蚂蚁金服，居然倒在了一个Java集合之Map上？
文章链接：http://soscw.com/index.php/essay/77845.html

亲，登录后才可以留言！

面试半年！三面阿里，四面蚂蚁金服，居然倒在了一个Java集合之Map上？

Map接口

1. 常见实现类结构

1.1 HashMap

1.2 LinkedHashMap

1.3 TreeMap

1.4 Hashtable

1.5 Properties

2. 存储结构的理解：

3. 常用方法

3.2元素查询的操作：

3.3 元视图操作的方法：

4. 内存结构说明：（难点）

4.1.3 HashMap的扩容

4.1.4 HashMap扩容时机

4.2 HashMap在JDK 8.0底层实现原理：

4.2.2 HashMap添加元素的过程：

4.2.3 HashMap的扩容机制:

4.2.4 JDK 8.0与JDK 7.0中HashMap底层的变化：

4.3 HashMap底层典型属性的属性的说明：

4.4 LinkedHashMap的底层实现原理

5. TreeMap的使用

6.使用Properties读取配置文件

最后

评论

热门文章

推荐文章

最新文章

置顶文章