集合中Set接口、数据结构
.Set接口特点:无序、不允许重复,是Collection接口的子接口 没有定义新方法,所有的方法都是Collection接口中所定义的方法 实现类HashSet存储采用哈希表的方式进行存储,HashSet采用HashCode算法来存取集合中的元素,因此具有比较好的读取和查找性能 LinkedHashSet是在HashSet的基础上添加一个额外的链表结构可以记录存储数据的顺序 TreeSet采用的是树状结构进行数据存储 HashSet类定义 数据的存储方式 常用算法 boolean add(E e)向集合Set中添加元素,注意不保证顺序
void clear()清空集合中的所有元素 boolean contains(Object o)判断集合中是否有指定的对象,同样需要hashCode和equals方法 int size()获取集合中的元素个数 Iterator iterator()用于遍历所存储的数据
HashSet的特征无序:不仅不能保证元素插入的顺序(如果需要顺序则可以使用LinkedHashSet),而且在元素在以后的顺序中也可能变化(这是由HashSet按HashCode存储对象(元素)决定的,对象变化则可能导致HashCode变化) 如果需要访问的顺序和插入的顺序一致,可以使用HashSet的子类LinkedHashSet不允许重复 [equals和hashcode] **结论:**当HashSet判定对象重复时,首先调用的是对象的hashCode方法,如果两个对象的hashCode值相同时,才调用equals进行判定。如果hashCode值不相等则不会调用equals判断。如果 hashcode相等而且equals为true,则后盖前 HashSet是线程非安全的,方法上没有同步约束 LinkedHashSet类定义
LinkedHashSet是HashSet的一个子类,LinkedHashSet也根据HashCode的值来决定元素的存储位置,但同时它还用一个链表来维护元素的插入顺序,插入的时候即要计算hashCode又要维护链表,而遍历的时候只需要按链表来访问元素 TreeSetTreeSet实现了SortedSet接口,顾名思义这是一种排序的Set集合 内部实现 基本用法
TreeSet的排序分两种类型,一种是自然排序,另一种是定制排序。
如果使用TreeSet时不会依靠hashcode和equals进行比较,相等性判断是依靠compareTo实现的 自然排序(在元素中写排序规则) TreeSet 会调用compareTo方法比较元素大小,然后按升序排序(从小到达)。所以自然排序中的元素对象,都必须实现了Comparable接口,否则会抛出异常。对于TreeSet判断元素是否重复的标准,也是调用元素从Comparable接口继承而来compareTo方法,如果返回0则是重复元素。Java的常见类都已经实现了Comparable接口 给Person类上添加针对Comparable接口的实现:考虑具体的业务规则,按照类中什么属性进行排序比较 数据结构哈希表Hash一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。例如使用指纹数据保证数据传输的可靠性 所有散列函数都有如下一个基本特性:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同。 在Java中任意一个对象都有一个hashCode()方法,可以获取任意一个对象的hash值 哈希冲突当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,就把它叫做碰撞(哈希碰撞)。 散列算法散列法Hashing是一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法。 由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中 String类型的定义 String类型中的hashCode方法的实现: 二叉树二叉搜索树(Binary Search Tree,简称 BST),BST是一种很常用的的二叉树。它的定义是:一个二叉树中,任意节点的值要大于等于左子树所有节点的值,且要小于等于右边子树的所有节点的值 主要针对链表的插入和删除很快,但是是查找数据却很慢的特点。树状结构最大的优势在于查找,但是插入和删除的效率都不太高
二叉树在极端情况下会退化为链表结构,为了避免出现这个问题,引入平衡树 AVL 树是一种平衡二叉树,平衡二叉树递归定义如下:
AVL树引入了所谓监督机制,就是在树的某一部分的不平衡度超过一个阈值后触发相应的平衡操作。保证树的平衡度在可以接受的范围内。 红黑树是一种近似平衡的二叉查找树,查找、删除、插入都快,树经常需要进行旋转达到平衡,但是平衡算法很复杂。 红黑树特征:
|
|