黑马程序员技术交流社区

标题: Set为什么要用哈稀表作为存储结构 [打印本页]

---

作者: 周刚    时间: 2012-7-13 23:56
标题: Set为什么要用哈稀表作为存储结构
Set集合为什么要用hash表作用底存的存储结构？
HashSet与ArrayList和LinkList比起来，在增删和查找速度方面各有什么优劣呢？

---

作者: 刘煜    时间: 2012-7-14 02:45
第一个问题：
Set接口是 Collection的一种扩展，它的常用具体实现有HashSet和TreeSet类。其中HashSet的底层数据结构式哈希表，原因是：在Set中的对象元素不能重复，也就是说你不能把同样的东西两次放入同一个Set容器中。对于HashSet，在存放元素的时候，HashSet会先会调用hashCode()方法，比较元素的哈希值是否相同；如果相同了，然后就比较元素的内容是否相同，会调用元素对象的equals方法，由于HashSet方法用到了哈希表的算法，所以HashSet的数据结构式哈希表，只有这样才能保证HashSet的对象元素不会重复。
特殊情况：由于一般情况下哈希表存放的是对象的地址，当存放的是自定对象时，因为对象的地址都不同，而内容可能相同，所以容易存放重复的对象。解决这样的问题，需要在自定义对象中重写hashCode()方法和equals方法。
TreeSet的底层数据结构式二叉树，放入其中的元素是按序存放的，这就要求你放入其中的对象是可排序的。用到了集合框架提供的另外两个实用Comparable和Comparator。一个类是可排序的，它就应该实现Comparable接口。有时多个类具有相同的排序算法，那就不需要在每分别重复定义相同的排序算法，只要实现Comparator接口即可。
第二个问题：
对于ArrayList：增删元素的时候会判断集合中的元素对象是否相同使用equals方法，用对象的equls方法与另一个对象相比，因此增删速度慢于LinkList，快于HashSet。由于ArrayList的底层数据结构是数组，有角标，其查找速度快于LinkList而慢于HashSet。
对于LinkList：由于其底层数据结构式链表，增删元素的时候只需要修改元素头尾的存储的地址就行，增删速度比ArrayList快；但其查找的时候，需要比较元素首尾存储的地址是否与前后元素的地址一致，因此查询速度慢于ArrayList和HashSet。
对于HashSet：由于其底层数据结构式哈希表，为了保证元素的唯一性，增删元素的时候HashSet会先会调用hashCode()方法，比较元素的哈希值是否相同，如果相同了，然后就比较元素的内容是否相同，会调用元素对象的equals方法，调用了两个方法，因此增删速度最慢。查询方面，HashSet是为优化查询速度而设计的，因为其用了“专为快速查找而设计”的散列函数，比ArrayList和LinkList快。
总结：HashSet在元素增删速度方面劣于ArrayList和LinkList，在查询速度方面是优于ArrayList和LinkList的。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2