欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Thinking in java:17 容器深入研究

程序员文章站 2024-03-17 17:45:22
...

1. Set和存储顺序

Thinking in java:17 容器深入研究

2. 理解Map

Thinking in java:17 容器深入研究

再次强调默认的Object.equal()只是比较对象的地址,所以如果要用自己的类作为HashMap的键,必须同时重载hashCode()和equal()方法。

3. 理解hashCode()

  使用散列的目的在于:想要使用一个对象来查找另一个对象。散列的价值在于速度(为什么使用散列):散列使得查询得以快速进行。

我们知道存储一组元素最快的数据结构是数组,所以使用数组来表示键的信息(并非键本身)。通过键对象生成一个数字(称为散列码,即hashCode()方法生成的数字),将其作为数组的下标。而这个数组中存放的是值的List,因为相同散列码的键所对应的值都存放在数组的这个下标中。不同的键可以产生相同的下标(散列码)。于是查询一个值的过程就是,使用hashCode方法计算出此键的散列码,那么就知道值所在的数组下标,然后到此下标中的List中使用equals()方法进行线性查询。

HashMap其实就是数组+List实现的。

那么设计hashCode()时最重要的元素是:无论何时,对同一个对象调用hashCode()方法都应生成同样的值。另外一个,好的hashCode()应该产生均匀分布的散列码。

4. 为什么HashMap是线程不安全的?

因为HashMap底层维护了一个数组,当多线程时对这个数组的操作是不安全的。

5. 不同接口的选择

   5.1 对List的选择

       将ArrayList作为默认首选,当程序需要经常从表中间进行插入和删除时才选用LinkedList。

       需要进行随机访问是,例如put()和set()操作时,和查询时,一般ArrayList的速度快,需要频繁插入和删除时,LinkedList的速度快。原因:ArrayList底层是数组支持,LinkedList是由双向链表实现的。ArrayList在插入时,必须创建空间并将移动它的引用,所以代价高。而LinkedList只需链接新的元素,而不必修改列表中的剩余元素,所以无论尺寸如何变化,其代价大致相同。

   5.2 对Set的选择

HashSet的性能基本上总是比TreeSet好,特别是在添加查询元素时,而这两个操作也是最重要的操作。TreeSet存在的唯一原因是它可以维持元素的排序状态。

HashSet的实现原理总结如下:

①是基于HashMap实现的,默认构造函数是构建一个初始容量为16,负载因子为0.75 的HashMap。封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。

②当我们试图把某个类的对象当成 HashMap的 key,或试图将这个类的对象放入 HashSet 中保存时,重写该类的equals(Object obj)方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致:当该类的两个的 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。

③HashSet的其他操作都是基于HashMap的。


LinkedHashSet


是基于链表实现的。对于插入操作,LinkedHashSet比HashSet的代价更高,这是由于维护链表所带来的额外开销造成的。


TreeSet

TreeSet采用的数据结构是红黑树,我们可以让它按指定规则对其中的元素进行排序。它又是如何判断两个元素是否相同呢?除了用equals方法检查两个元素是否相同外,还要检查compareTo方法是否返回为0。
所以如果对象要存放到Tree集合里,需要在重写compareTo时,把相同的对象的比较值定为0,防止相同的元素被重复添加进集合中。

面试分享:
HashSet在源代码内是如何实现不add相同的元素的?

理论上我们都知道,它的内部是根据equals()返回值和hashCode()的值是否相同两个方法来判断两个对象是否相同的。而源代码上,HashSet内部用了一个HashMap作存储,add()方法内是调用了map的put()方法,map的put()方法会检查这个键是否已存在,若是则返回该键之前的值,并更新成新值,若不是则返回null,但这个键是不会发生改变的。所以,在源代码里,HashSet的add()方法是根据map的put返回值来判断添加元素是否成功的。

HashSet导致的内存泄漏

把一个对象存储进hashSet集合后,修改这个对象中参与计算hash的变量的值,这时这个对象的hash值也会随之改变,那么这么对象可以正常地被删除吗?下面用代码试一下:

public class MPoint {  
     private int x;  
     private int y;  
  
     public MPoint() {  
     }  
  
     public MPoint( int x, int y) {  
            this. x = x;  
            this. y = y;  
     }  
  
     public int getX() {  
            return x;  
     }  
  
     public void setX(int x) {  
            this. x = x;  
     }  
  
     public int getY() {  
            return y;  
     }  
  
     public void setY(int y) {  
            this. y = y;  
     }  
  
     @Override  
     public int hashCode() {  
            final int prime = 31;  
            int result = 1;  
            result = prime * result + x; //x参与计算hash值  
            return result;  
     }  
  
     @Override  
     public boolean equals(Object obj) {  
            if ( this == obj)  
                 return true;  
            if ( obj == null)  
                 return false;  
            if (getClass() != obj.getClass())  
                 return false;  
           MPoint other = (MPoint) obj;  
            if ( x != other. x)  
                 return false;  
            if ( y != other. y)  
                 return false;  
            return true;  
     }  
}  

主函数类测试,在一个HashSet集合中添加三个元素,mp1、mp2、mp3,并进行其中属性的修改和输出测试

public class HashSetTest {  
  
     public static void main(String[] args) {  
           HashSet<MPoint> set = new HashSet<MPoint>();  
           MPoint mp1 = new MPoint(1, 6);  
           MPoint mp2 = new MPoint(2, 7);  
           MPoint mp3 = new MPoint(1, 6);  
  
            set.add( mp1);  
            set.add( mp2);  
            set.add( mp3);  
            set.add( mp1);  
  
           System. out.println( set.size()); // 结果为2  
  
            mp1.setX(3);  
            set.remove( mp1);  
           System. out.println( set.size()); // 结果还是为2,说明没有删除成功  
           System. out.println( set.contains( mp1)); // 结果为false,修改了参与计算hash值的变量,其对象不能再被找到  
           System. out.println( set.remove( mp1)); // 结果为false,修改了参与计算hash值的变量,其对象不能被删除  
  
            mp2.setY(2);  
           System. out.println( set.contains( mp2)); // 结果为true,没有修改关键属性的对象可以被找到  
           System. out.println( set.remove( mp2)); // 结果为true,没有修改关键属性的对象可以被删除  
           System. out.println( set.size()); // 结果还是为1  
     }  
}  

输出:

2  
2  
false  
false  
true  
true  
1  

可以看出已经发生了内存泄漏了,mp1对象不能被正常删除。

   5.3 对Map的选择

除了IdentityHashMap,所有的Map实现的插入操作都会随着Map尺寸的变大而明显变慢。但是,查找的代价通常比插入要小得多,这是个好消息,因为我们执行查找元素的操作要比执行插入元素的操作多得多。

HashMap与Hashtable的性能大体相当。因为HashMap是用来替代Hashtable的,他们使用相同的底层存储和查找机制。

TreeMap通常比HashMap慢,但它能根据key来排序。

LinkedHashMap在插入时比HashMap慢一点,因为它维护散列数据结构的同时还要维护链表(以保证插入顺序)。正是由于这个列表,使得其迭代速度更快。LinkedHashMap是HashMap的一个子类,它保留插入的顺序。LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。 LinkedHashMap实现与HashMap的不同之处在于,后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序。

HashMap的性能因子:

负载因子:尺寸/容量。负载轻的表产生冲突的可能性小。当达到负载因子的水平时,容器自动增加其容量,并重新将现有对象分布到新的桶位集中,这被称为“再散列”。

桶:一个数组的某一项就是一个桶,如a[0]、a[1]都是桶