A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

本帖最后由 小石姐姐 于 2018-8-3 10:07 编辑



常见的数据结构:栈 ,队列 ,数组 ,链表和红黑树
       栈: stack,又称堆栈,是一种  运算受限 的线性表
       特点: 1.先进后出
                2.栈的入口,出口都是栈的顶端位置
       队列: queue 也是一种  运算受限  的线性表
       特点: 1.先进先出
                2.队列的入口,出口各占一侧
       数组: Array,有序的元素序列
       特点: 1.查找元素快(通过索引)
                2.增删元素慢(需要创建新数组)
       链表: linked list,由节点node(链表中每个元素称为节点)组成,节点可以在运行时i动态生成.
               每个节点包括两个部分: 一个是存储数据元素的数据域
                                                  另一个是存储下一个节点地址的指针域.包括单向和双向链表.
       特点: 1. 多个节点之间,通过地址进行链接
                2. 查找元素慢
                3. 增删元素快
       红黑树: binary tree,是每个节点不超过2的有序树(tree)
       红黑树的约束:
               1. 节点可以是红色的或者黑色的
               2. 根节点是黑色的
               3. 叶子节点(特指空节点)是黑色的
               4. 每个红色节点的子节点都是黑色的
               5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
       特点:  速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍

List接口:
     特点:
          1. 它是一个存取有序的集合;
          2. 带有索引
          3. 集合中可以有重复的元素,通过元素的equals方法.来比较是否为重复的元素
      常用方法:
[Java] 纯文本查看 复制代码
pubilc void add (int index, E element) : 将指定的元素,添加到该集合中的指定位置上.
public E get (int index) : 返回集合中指定位置的元素.
public E remove (int index) : 移除列表中指定位置的元素,返回的是被移除的元素.
Public E set (int index, E element) : 用指定元素替换集合中指定位置的元素,返回值的更新前的元素.

ArrayList集合的特点:
           ArrayList底层的数据结构:数组
                特点:
                          查询快
                          增删慢
                          线程不安全,效率高
               使用场景:
                          存储的数据查询多,增删少的场景

LinkedList集合的特点:
            LinkedList底层的数据结构:链表
                 特点:
                          查询慢
                          增删快
                          线程不安全, 效率高
                适用场景:
                          存储的数据查询少, 增删多的场景
特有成员方法(主要操作开头和末尾元素):
[Java] 纯文本查看 复制代码
void addFirst(E e): 将指定元素插入此列表的开头[/size][/font][/align][align=left][font=微软雅黑][size=3]void addLast(E e): 将指定元素添加到此列表的结尾
E getFirst(): 返回此列表的第一个元素
E getLast(): 返回此列表的最后一个元素
E removeFirst(): 移除并返回此列表的第一个元素
E removeLast(): 移除并返回此列表的最后一个元素
E pop(): (其实就是removeFirst())从此列表所表示的栈中弹出一个元素
void push(E e): (其实就是addFirst())将元素添加到此列表所表示的栈中

Vector集合
                 Vector底层的数据结构:数组
                 Vector的特点:
                          查询慢
                          增删快
                          线程安全, 效率低
                 Vector目前几乎没人使用

Set集合体系
                 HashSet集合
                 Set集合体系特点:
                          1. 元素不可重复
                          2. 没有索引
                 HashSet特点:
                          1. 元素不可重复
                          2. 没有索引
                          3. 元素存取无序 (存入和取出顺序有可能不一致)
                          4. 底层采用 哈希表 结构. (查询快)
                 哈希表 = 数组 + 链表或红黑树
                 常用方法:
[Java] 纯文本查看 复制代码
boolean add(E e): 添加元素, 根据元素的
hashCode()和equals()方法判断是否重复. 重复则不添加并返回false, 不重复则添加并返回true
哈希值:
              一个十进制数值, 一般是通过将该对象的内部地址转换成一个整数来实现的
             public native int hashCode();
             可以调用系统本地代码(C++)计算出一个对象地址的哈希值hashCode()方法的作用
             方法内部的算法用于将对象计算为一个哈希值, 便于根据哈希值比较对象是否"相等"
             哈希值主要是为了提高对象存储在 哈希表 中的效率
             注意:
                          1. 如果我们不满意Object中的哈希值计算方法, 可以重写hashCode()方法.
                              但在Java代码中不能直接重写带有 native 的方法, 重写时应该将native 去掉
                              @Override
                              public int hashCode() {}
                          2. hashCode() 方法有可能将"不同的对象"计算出"相同的哈希值", 这称为"哈希冲突",
                              在出现冲突后, 一般再通过 equals() 方法来继续判断对象是否"相等

             HashSet集合存储数据的结构: 哈希表
             哈希表 = 数组+链表/红黑树

可变参数
             JDK 5 出现. 指同一个类型参数个数可变的参数
                          可变参数的本质就是一个"数组"
             格式: 用在方法的参数中
                          修饰符 返回值类型 方法名(参数类型... 变量名) {
                                       // 可以直接将 变量名 当作 数组名 使用
                          }
             注意事项:
                          1. 可变参数可以传递的参数个数, 可以是 0个, 1个, 多个
                          2. 一个方法的参数列表中, 只能有一个可变参数
                          3. 如果方法的参数有多个, 可变参数必须写在参数列表的最后

Collections集合工具类
             Collections集合工具类: addAll(), shuffle()
             java.util.Collections类: 操作集合的工具类
             静态方法:
[Java] 纯文本查看 复制代码
static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素
static void shuffle(List<?> list) :打乱集合顺序
static <T> void sort(List<T> list) :将集合中元素按照默认规则排序
static <T> void sort(List<T> list,Comparator<? super T> ) :将集合中元素按照指定规则排序

             Collections集合工具类: sort(List list)
                          sort(List<T> list): 默认按照"升序"将元素排序. 数字, 字母, 都可以按照升序排序
                          自定义JavaBean对象默认不能排序, 因为不知道如何比较哪个对象大, 哪个对象小
                          自定义JavaBean对象要想排序, 需要实现 Comparable<E> 接口, 重写 int compareTo(E e) 方法
                          大小的比较通过 compareTo() 方法的返回值确定:

                          负数: 当前元素比被比较元素小
                          0: 当前元素与被比较元素相等
                          正数: 当前元素比被比较元素大
             规则:
                          this-参数: 升序
                          参数-this: 降序


Comparable接口和Comparator接口区别
             Comparable: 让JavaBean自身具有可比较性 (自己和其他人比)
             Comparator: 定义一个比较器类, 用比较器对象比 (让第三个人来帮两个人比较)
             Comparator使用方式:
             定义类作为比较器, 实现Comparator接口, 重写int compare(E o1, E o2)方法, 泛型为要比较的元素的类型
             在Collections.sort(List<T> list,Comparator<? super T>)方法中传入自定义比较器对象
             规则:
                          o1-o2: 升序
                          o2-o1: 降序



java.util.Map接口: 双列集合的顶层
          成员方法:
[Java] 纯文本查看 复制代码
                V put(K key, V value): 添加/修改键值对. 如果键存在, 则用新值替换已有值
                V remove(Object key): 根据键删除键值对, 返回被删除元素的值
                V get(Object key): 根据键获取值. 如果键不存在, 则返回null
                boolean containsKey(Object key): 判断是否包含指定的键
                Set<K> keySet(): 获取Map集合中所有的键, 存储到Set集合中
                Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)

        
          JDK 9对于集合初始化的优化
                java.util.List
                        静态方法
                        static List<E> of(E... e): 返回包含指定元素的 不可变List 集合
                        
                java.util.Set
                        静态方法
                        static Set<E> of(E... e): 返回包含指定元素的 不可变Set 集合
                        
                java.util.Map
                        静态方法
                        static Map<K, V> of(K k1, V v1): 返回包含指定键值对的 不可变Map 集合


        Map集合概述:
                java.util.Map<K, V>接口
                Map集合特点:
                        1. 是双列集合, 一个元素包含两个值 (键key, 值value)
                        2. key和value的类型可以相同, 也可以不同
                        3. key不允许重复, value可以重复
                        4. key和value是一一对应的, 一个键只能对应一个值
                Map集合适合存储一对一关系的数据
        Map常用子类:
                java.util.Map<K, V>接口: 双列集合的根接口, 规定了共性的方法
                        |_ HashMap<K, V>类: 底层哈希表. key存取无序不可重复
                                |_ LinkedHashMap类: 底层哈希表+链表. key存取有序不可重复
                        映射: 键和值的对应关系 mapping
                        HashSet底层使用的就是HashMap
                        LinkedHashSet底层使用的就是LinkedHashMap
        Map中常用方法:
                Map<String, Phone> map = new HashMap<>();
                map.put("张三", p1);
                map.put("张三", p2);
                java.util.Map接口: 双列集合的顶层
                        成员方法
[Java] 纯文本查看 复制代码
                        V put(K key, V value): 添加/修改键值对. 如果键存在, 则用新值替换已有值
                        V remove(Object key): 根据键删除键值对, 返回被删除元素的值
                        V get(Object key): 根据键获取值. 如果键不存在, 则返回null
                        boolean containsKey(Object key): 判断是否包含指定的键
                        Set<K> keySet(): 获取Map集合中所有的键, 存储到Set集合中
                        Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的Entry对象的集合(Set集合)

        Map遍历方式一:keySet()方法实现通过键找值
                Set<K> keySet(): 获取Map集合中所有的键, 存储到Set集合中
                keySet()遍历步骤:
                        1. Map对象调用 keySet() 方法, 获取包含所有key的Set集合
                        2. 遍历Set集合, 获取每个key
                        3. 通过Map对象调用 get(Object key) 方法根据key获取到value
                        
[Java] 纯文本查看 复制代码
Map<String, String> map = new HashMap<>();
// keySet()遍历
Set<String> keys = map.keySet();
for (String key : keys) {
       // 通过每个键获取值
       String value = map.get(key);
       // 打印当前键值对
       System.out.println(key + "=" + value);
       }

        Entry键值对对象介绍:
                 java.util.Map.Entry接口:
                        常用成员方法:
                        K getKey(): 获取Entry对象中的键
                        V getValue(): 获取Entry对象中的值
                Entry对象就是一个节点, 节点中存储了key和value
                拿到一个Entry对象就可以从中获取key和value
        HashMap中Entry实现类
[Java] 纯文本查看 复制代码
static class Node<K,V> implements Map.Entry<K,V> {
          final int hash;
          final K key;
          V value;
          Node<K,V> next;
          public final K getKey() {
                return key;
          }
          public final V getValue() {
                return value;
          }
}

         java.util.Map接口
                Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)
                        
    Map遍历方式二:通过entrySet()获取对象形式遍历:
         java.util.Map接口
               Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)
         entrySet()方法遍历Map步骤:
                        1. Map对象调用 entrySet() 获取包含所有Entry对象的Set集合
                        2. 遍历Set集合, 获取每个Entry对象
                        3. 调用Entry对象的 getKey() 和 getValue() 方法获取键和值
[Java] 纯文本查看 复制代码
Map<String, String> map = new HashMap<>();
        // keySet()遍历
        Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry : entries) {
        // 通过Entry对象获取每个键值对
        String value = entry.getKey();
        String value = entry.getValue();
        // 打印当前键值对
        System.out.println(key + "=" + value);

        JDK9对集合添加的优化:
                使用集合添加大量元素时, 反复add(...)比较麻烦.
                JDK 9 为集合提供了一些静态方法, 可以方便的对集合进行初始
                        java.util.List
                                静态方法:
                              static List<E> of(E... e): 返回包含指定元素的 不可变List 集合
                        java.util.Set
                                静态方法
                               static Set<E> of(E... e): 返回包含指定元素的 不可变Set 集合
                        java.util.Map
                                静态方法
                              static Map<K, V> of(K k1, V v1, ...): 返回包含指定键值对的 不可变Map 集合
               注意:
                     1. of() 方法只适用于List接口, Set接口, Map接口, 不适用于接接口的实现类
                     2. of() 方法的返回值是一个不能改变的集合, 集合不能再使用 add(), put() 方法添加元素, 会抛出异常
                     3. Set接口和Map接口在调用 of() 方法的时候, 不能有重复的元素, 否则会抛出异常
                将 不可变集合 的元素转移到常见集合实现类中:
                       List

                   
[AppleScript] 纯文本查看 复制代码
    ArrayList<Integer> list = new ArrayList<>(List.of(1,2,3));[/align]                        Set
                       HashSet<Integer> set = new HashSet<>(Set.of(1,2,3));
                        Map
                       HashMap<Integer, String> map = new HashMap<>(Map.of(1,"a",2,"b"));
        今日目标:
                能够说出Map集合特点:
                        Map接口双列集合的顶层
                        特点:
                        Map存储元素是键值对方式(key-value)
                        Map中key不能重复(唯一), 键值对是一一对应的, 一个键对应一个值
                使用Map集合添加方法保存数据:
                        map.put(键, 值);
                        添加键值对: map中没有这个键时, 返回null
                        修改键值对: map中已经有该键, 返回的是被替换的值
                使用”键找值”的方式遍历Map集合:
                        
[Java] 纯文本查看 复制代码
keySet()
Set keySet = map.keySet();
 for (键的类型 key : keySet) {
          // 通过键获取值
          值的类型 value = map.get(key);
          }

                使用”键值对”的方式遍历Map集合:
                        
[Java] 纯文本查看 复制代码
Entry对象[/align][align=left]Set<Entry> entrySet = map.entrySet();[/align]
[align=left]for (Entry entry : entrySet) {[/align]
[align=left]// 通过entry对象获取键和值[/align]
[align=left]键的类型 key = entry.getKey();[/align]
[align=left]值的类型 value = entry.getValue();[/align]
[align=left]}




您需要登录后才可以回帖 登录 | 加入黑马