常见数据结构的区别
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
相关博文
常见数据结构的区别