数据结构与集合源码

1.数据结构概述

数据结构是指数据元素之间的关系的一种组织形式，是一种特定的数据的组织方式和存储结构。它是计算机存储、组织和操作数据的基础，可以有效地提高数据的存储和处理效率。

数据结构可以分为线性结构和非线性结构两种。线性结构中的数据元素之间存在一对一的关系，如线性表、栈、队列等；非线性结构中的数据元素之间存在一对多或多对多的关系，如树、图等。

数据结构的设计和选择需要考虑数据的特点和操作的需求。通常需要综合考虑数据元素的存储、查找、插入、删除等操作的效率，选择适合的数据结构来实现。

常见的数据结构有数组、链表、栈、队列、树、图等。每种数据结构都有自己的特点和适用场景，选择合适的数据结构可以提高程序的效率和性能。

数据结构是计算机科学的重要基础，它是算法设计和分析的基础，也是其他计算机科学领域的基础。掌握数据结构的基本概念和设计方法，对于理解和解决实际问题具有重要意义。

1.1数据间的逻辑关系

1.2数据的存储结构 

常见的数据结构存储结构有以下几种：

1. 数组（Array）：一段连续的内存空间，可以通过下标直接访问元素，适合随机访问，但插入和删除元素比较慢，时间复杂度为O(n)。

2. 链表（Linked List）：由节点组成的数据结构，每个节点包含数据和指向下一个元素的指针，插入和删除元素比较快，但随机访问效率较低，时间复杂度为O(n)。

3. 栈（Stack）：一种先进后出的数据结构，只允许在一端进行插入和删除操作，通常使用数组或链表实现。

4. 队列（Queue）：一种先进先出的数据结构，只允许在一端进行插入操作，另一端进行删除操作，通常使用数组或链表实现。

5. 树（Tree）：一种非线性的数据结构，由节点和边组成，每个节点可以有多个子节点，常见的有二叉树、二叉搜索树、平衡二叉树等。

6. 图（Graph）：由节点和边组成的数据结构，节点之间可以有多个连接，可用于表示网络、地图等复杂关系。

7. 哈希表（Hash Table）：通过哈希函数将键映射到存储位置，可以快速插入、删除和查找。

8. 堆（Heap）：一种特殊的树形数据结构，可以高效地找到最大或最小值，常用于实现优先队列。

9. 链表（LinkedList）：将数据按节点顺序存储在一连串的内存空间中，节点包含数据和指向下一个节点的指针。

10. 图（Graph）：由节点和边组成的数据结构，节点之间可以有多个连接。

这些存储结构可以根据具体的应用场景选择合适的数据结构进行存储和操作，以提高算法的效率和性能。

2.List实现类源码分析

2.1ArrayList

2.1.1ArrayList的特点

> 实现的List的接口，存储有序的，可重复的数据。

> 底层使用Object[] 数组存储。

> 线程不安全的。

2.1.2ArrayList源码分析

JDK7版本

JDK8版本

3.Map实现类源码分析

3.1HashMap

3.1.1HashMap的特点

1. HashMap是基于哈希表的数据结构，使用哈希算法将元素的键映射到哈希表中的索引位置。

2. HashMap允许存储键值对，其中每个键只能出现一次，并且键和值可以是任意类型的对象。

3. HashMap提供了快速的插入、删除和查找操作，平均时间复杂度为O(1)。

4. HashMap并不保证元素的顺序，即元素的顺序可能与插入顺序不一致。

5. HashMap允许存储null键和null值。

6. HashMap的初始容量和负载因子可以调整，以提供更高的性能和空间利用率。

7. HashMap是非线程安全的，不适用于多线程环境下的并发操作。如果需要在多线程环境中使用HashMap，可以考虑使用ConcurrentHashMap。

8. HashMap的内部实现采用数组和链表或红黑树的组合结构，用于解决哈希冲突问题。

3.1.2HahMap源码分析

HahMap源码分析

HahMap是一个哈希表的实现，用于存储键值对。

以下是HahMap的基本结构：

public class HashMap<K, V> {
    // 内部数组，用于存储键值对
    private Node<K, V>[] table;
    // 存储节点的数量
    private int size;
  
    // 节点类，用于存储键值对
    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;
  
        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
  
    // 构造函数，初始化内部数组
    public HashMap() {
        table = new Node[16];
        size = 0;
    }

    // put方法，用于插入键值对
    public void put(K key, V value) {
        // 计算哈希码
        int hash = Math.abs(key.hashCode() % table.length);
        // 创建新的节点
        Node<K, V> newNode = new Node<>(key, value);
        
        // 如果哈希桶为空，则直接插入新节点
        if (table[hash] == null) {
            table[hash] = newNode;
            size++;
        } else {
            // 如果哈希桶不为空，则遍历链表查找键值是否存在
            Node<K, V> current = table[hash];
            while (current != null) {
                // 如果键值已存在，则更新值
                if (current.key.equals(key)) {
                    current.value = value;
                    return;
                }
                current = current.next;
            }
            
            // 键值不存在，则将新节点插入到链表尾部
            Node<K, V> tail = table[hash];
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = newNode;
            size++;
        }
    }
  
    // get方法，用于获取键对应的值
    public V get(K key) {
        // 计算哈希码
        int hash = Math.abs(key.hashCode() % table.length);
        // 遍历链表查找键值对
        Node<K, V> current = table[hash];
        while (current != null) {
            // 键值存在，则返回对应的值
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        // 键值不存在，则返回null
        return null;
    }
  
    // remove方法，用于删除键值对
    public void remove(K key) {
        // 计算哈希码
        int hash = Math.abs(key.hashCode() % table.length);
        // 遍历链表查找键值对
        Node<K, V> current = table[hash];
        Node<K, V> prev = null;
        while (current != null) {
            // 键值存在，则删除节点
            if (current.key.equals(key)) {
                if (prev == null) {
                    table[hash] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return;
            }
            prev = current;
            current = current.next;
        }
    }
  
    // size方法，用于获取哈希表中节点的数量
    public int size() {
        return size;
    }
}

总的来说，HahMap的实现基于一个数组，每个数组元素是一个链表的头节点。当插入新的键值对时，会根据键的哈希码计算出对应的数组下标，然后将新节点插入到链表的尾部。当获取键对应的值时，会根据键的哈希码找到对应的链表，并遍历链表查找键值对。当需要删除键值对时，会根据键的哈希码找到对应的链表，并遍历链表查找待删除的节点。

HahMap支持动态扩容，当哈希表中节点的数量超过阈值时，会将数组的大小扩大一倍，并重新计算所有节点的哈希码和数组下标。这样做的目的是为了使哈希表的负载因子保持在一个较小的范围内，减小哈希冲突的概率，提高查询效率。

总结来说，HahMap的实现主要基于数组和链表，并且支持动态扩容，具有较好的查询和插入性能。

添加，修改的过程

> 将(key1,value1)添加到当前的map中，

首先会通过key1所在类的hashcode()方法计算出key1的哈希值1，然后在通过某种算法(hash())之后，在算出key1的哈希值2.

> 然后根据哈希值2再经过某种算法（indexFor()）之后，确定(key1,value1)在数组table中索引的位置。

      情况1：如果此索引上没有元素，则(key1,value1)添加成功。

      如果(key1,value1)在table中的索引已经存在(key2,value2)，则会判断key1和key2的哈希值2.

                  如果key1和key2的哈希值2不同，则(key1,value1)添加成功。

                  情况2： 如果key1和key2的哈希值2相同，则比较key1和key2的equals()。需要调用key1所在类的equals()方法，将key2作为参数传递出去。

                  调用 equals()方法，返回false，则(key1,value1)添加成功。

                                情况3：调用 equals()方法，返回true，则认为key1和key2相同，默认情况下，value1替换原有的value2。

什么时候使用红黑树？

如果索引位置上元素的个数达到8个，并且数组的长度达到64时，我们将此索引位置的多个元素改为使用红黑树结构。

原文地址：https://blog.csdn.net/2302_78998188/article/details/143688823

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！