常见数据结构的区别

常见数据结构的区别

1 1:集合
  2     Collection(单列集合)
  3         List(有序,可重复)
  4             ArrayList
  5                 底层数据结构是数组,查询快,增删慢
  6                 线程不安全,效率高
  7             Vector
  8                 底层数据结构是数组,查询快,增删慢
  9                 线程安全,效率低
 10             LinkedList
 11                 底层数据结构是链表,查询慢,增删快
 12                 线程不安全,效率高
 13         Set(无序,唯一)
 14             HashSet
 15                 底层数据结构是哈希表。
 16                 哈希表依赖两个方法:hashCode()和equals()
 17                 执行顺序:
 18                     首先判断hashCode()值是否相同
 19                         是:继续执行equals(),看其返回值
 20                             是true:说明元素重复,不添加
 21                             是false:就直接添加到集合
 22                         否:就直接添加到集合
 23                 最终:
 24                     自动生成hashCode()和equals()即可
 25                     
 26                 LinkedHashSet
 27                     底层数据结构由链表和哈希表组成。
 28                     由链表保证元素有序。
 29                     由哈希表保证元素唯一。
 30             TreeSet
 31                 底层数据结构是红黑树。(是一种自平衡的二叉树)
 32                 如何保证元素唯一性呢?
 33                     根据比较的返回值是否是0来决定
 34                 如何保证元素的排序呢?
 35                     两种方式
 36                         自然排序(元素具备比较性)
 37                             让元素所属的类实现Comparable接口
 38                         比较器排序(集合具备比较性)
 39                             让集合接收一个Comparator的实现类对象
 40     Map(双列集合)
 41         A:Map集合的数据结构仅仅针对键有效,与值无关。
 42         B:存储的是键值对形式的元素,键唯一,值可重复。
 43         
 44         HashMap
 45             底层数据结构是哈希表。线程不安全,效率高
 46                 哈希表依赖两个方法:hashCode()和equals()
 47                 执行顺序:
 48                     首先判断hashCode()值是否相同
 49                         是:继续执行equals(),看其返回值
 50                             是true:说明元素重复,不添加
 51                             是false:就直接添加到集合
 52                         否:就直接添加到集合
 53                 最终:
 54                     自动生成hashCode()和equals()即可
 55             LinkedHashMap
 56                 底层数据结构由链表和哈希表组成。
 57                     由链表保证元素有序。
 58                     由哈希表保证元素唯一。
 59         Hashtable
 60             底层数据结构是哈希表。线程安全,效率低
 61                 哈希表依赖两个方法:hashCode()和equals()
 62                 执行顺序:
 63                     首先判断hashCode()值是否相同
 64                         是:继续执行equals(),看其返回值
 65                             是true:说明元素重复,不添加
 66                             是false:就直接添加到集合
 67                         否:就直接添加到集合
 68                 最终:
 69                     自动生成hashCode()和equals()即可
 70         TreeMap
 71             底层数据结构是红黑树。(是一种自平衡的二叉树)
 72                 如何保证元素唯一性呢?
 73                     根据比较的返回值是否是0来决定
 74                 如何保证元素的排序呢?
 75                     两种方式
 76                         自然排序(元素具备比较性)
 77                             让元素所属的类实现Comparable接口
 78                         比较器排序(集合具备比较性)
 79                             让集合接收一个Comparator的实现类对象
 80     
 81 2.关于集合选取原则
 82     
 83     是否是键值对象形式:
 84         是:Map
 85             键是否需要排序:
 86                 是:TreeMap
 87                 否:HashMap
 88             不知道,就使用HashMap。
 89             
 90         否:Collection
 91             元素是否唯一:
 92                 是:Set
 93                     元素是否需要排序:
 94                         是:TreeSet
 95                         否:HashSet
 96                     不知道,就使用HashSet
 97                     
 98                 否:List
 99                     要安全吗:
100                         是:Vector
101                         否:ArrayList或者LinkedList
102                             增删多:LinkedList
103                             查询多:ArrayList
104                         不知道,就使用ArrayList
105             不知道,就使用ArrayList
106             
107 3:集合的常见方法及遍历方式
108     Collection:
109         add()
110         remove()
111         contains()
112         iterator()
113         size()
114         
115         遍历:
116             增强for
117             迭代器
118             
119         |--List
120             get()
121             
122             遍历:
123                 普通for
124         |--Set
125     
126     Map:
127         put()
128         remove()
129         containskey(),containsValue()
130         keySet()
131         get()
132         value()
133         entrySet()
134         size()
135         
136         遍历:
137             根据键找值
138             根据键值对对象分别找键和值
139

常见数据结构的区别
标签: