`

经典容器 数组/链表/队列/散列表/映射表,及相关内容的排序方式

阅读更多

Java 经典容器 数组/链表/队列/散列表/映射表,及相关内容的排序方式

 了解java容器的必要性:
              javaEE开发大家经常用的也就是 数组,ArryList,Set等,其它的就用的很少了
            或是没有听说过。
              多了解一些内容,对于同一问题的解决可能拿出更优的解决方案,
            优秀的代码能够给与程序性能、用户体验的提升,优秀的解决方案能够
            让咱们轻轻松松解决问题。
            
            性能与解决方案都取决于我们经验的积累,也就是我们知识的积累。
            
 因为是学习,所以很多地方可能不到位或是错误的地方大家指正,一定要指正啊!!

 我学习的基本思路是:
          理论理解,经典实现举例,代码练习及结果,对应例子的使用场景,与使用中与之关联较紧密内容的拓展。
 
  大致内容:数组,链表,队列,散列集,映射表,链接散列集,链接映射表 
 
  容器:就是不同数据结构存储的不同实现。
 
(一)链表:包含3部分,data、next、previous 三部分都是双向链表
 
     特性:高效利用内存,新增、修改、删除效率较高,因为只是涉及到数据域前链存储地址或后链存储地址等地址指向的
        变更。
        不支持快速随机访问(就是通常用的get),如果为快速随机访问且能够提供下标最好用数组或ArrayList
        不是线程安全的,多线程中需要使用Collections.synchronizedList进行包装或自己实现线程同步方法
        Collections工具类中提供的同步方法
        List list = Collections.synchronizedList(new LinkedList(...));
        然后其它线程对list可以同时进行操作,如list.add() list.remove() ....
        
     使用场景:堆栈、队列或双端队列。
     
     例:LinkedList
       默认含有List接口提供的方法,调用add方法时默认数据被放入链尾
       实现了Queue Deque 队列接口。
       
       方法
          boolean add(E e):          将指定元素添加到此列表的结尾。
              add(int index, E element):在此列表中指定的位置插入指定的元素。
              addLast(E e):       将指定元素添加到此列表的结尾。
              addFirst(E e):       将指定元素插入此列表的开头。
          boolean offer(E e):        将指定元素添加到此列表的末尾(最后一个元素)。
          boolean offerFirst(E e):      在此列表的开头插入指定的元素。
          boolean offerLast(E e):      在此列表末尾插入指定的元素。
              push(E e):压栈
          由于实现了List Queue Deque 等接口,所以同一操作方法也比较多,区别在于是否知道操作成功与否
          及抛出的异常信息

       作为队列能够提供:能够根据需要提供各种灵活的进出策略,
       比如: FIFO(先进先出) LIFO(后进先出)
       
(二) 队列
     :队列是特殊的线性表,在表头删除在表尾删除
      自认为链表结构都是双端队列,数组结构可以理解为单向队列
      双端队列,有限队列,有限双端队列,优先级队列都可以用字面去理解、
      
     特性:  可以同时在表头删除元素在表尾添加元素。
     
          队列还提供其他的插入、提取和检查操作。每个方法都存在两种形式:一种抛出异常(操作失败时),
        另一种返回一个特殊值(null 或 false,具体取决于操作)。插入操作的后一种形式是用于专门为有容量
        限制的 Queue 实现设计的;在大多数实现中,插入操作不会失败。
        
          队列通常(但并非一定)以 FIFO(先进先出)的方式排序各个元素。不过优先级队列和 LIFO 队列(或
        堆栈)例外,前者根据提供的比较器或元素的自然顺序对元素进行排序,后者按 LIFO(后进先出)的方式对
        元素进行排序。无论使用哪种排序方式,队列的头 都是调用 remove() 或 poll() 所移除的元素。在 FIFO
        队列中,所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现
        必须指定其顺序属性。
        
     使用场景:任务排队处理,批量任务处理,线程池中任务的处理
                其实就是有先后的任务处理,或数据的批量处理
               
      队列接口 Queue Java源码中提供的队列实现基本都实现了Queue及后续对Queue拓展的Deque等
     
      举例:LinkedList
         AbstractQueue
         ArrayBlockingQueue
         ArrayDeque
        ArrayBlockingQueue
        PriorityQueue(优选级队列)
        等
        
     
      队列提供的方法:
      通用:插入 add(e) offer(e)
         移除 remove() poll()
         检查 element() peek()  
         
          boolean add(E e) :成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
          boolean offer(E e) 当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
          E remove()  获取并移除此队列的头。
          E poll() 获取并移除此队列的头,如果此队列为空,则返回 null。
          E element()  获取,但是不移除此队列的头。
          E peek() 获取但不移除此队列的头;如果此队列为空,则返回 null。
         
         
      拓展:优先级队列:使用堆数据结构的队列,堆是一个可以自我调整的二叉树,
               树执行add remove操作都可以让最小元素移动到根,不用排序
               
           优先级队列中可以保存实现了comparable接口的对象,
           也可以保存指定排序方式实现Comparator接口的对象。
          
           优先级队列 PriorityQueue
          
           例:PriorityQueue<XX> pq = new PriorityQueue<XX>();
              pq.add(new XX);'
              打印get 看获取出来是不是最小的对象。
             
(三) 散列表
     :可以快速的查找所需要的对象,散列表为每个对象计算出一个散列码hash code 根据对象实例域产生的整数
     自定义类需要实现hash code方法,实现的hash code方法必须与equals方法兼容
     散列表用链表数组实现,每个列表被称作桶 hashcode%桶的数目=保存元素桶的索引
     我理解的桶就是 一个双数组,根据key在数组中的下标,来取另一个数组的值
     Entry(int h,Key key,Value value,Entry<K,V> next) 表感觉是指的Entry []
     
     散列集的默认实现:HashSet
     1.HashSet是无序的
     2.在数据大时存储效率较高
     
        public HashSet() {
        map = new HashMap<E,Object>();
       }
             
    TreeSet
   TreeSet排序方式是升序存储对象类必须实现了Compareable接口的compare to方法
   也可以通过指定对象排序方式,通过指定使用Comparator类接口的compare方法
   new TreeSet(object,new Comparator{public int compare(Obj1,Obj2){xxxxx}})
   
   WeakHashMap多用于缓存,存的值key 是使用了java的WeakReference
   软引用 SoftReference
   弱引用WeakReference

   WeakHashMap的key的排序也可以使用Compareable或Comparator方法进行排序,

 

  LinkedHashMap链接映射表:

  LinkedHashMap实现了LRU缓存算法,最近使用原则,丢弃长时间没访问的数据项,

  通过重写父类方法:removeEldestEntry(Map.Entry<K,V> eldest){}方法实现,

 

 

 


   

   
              
 
 
       
  
       

分享到:
评论

相关推荐

    C++散列表实现电话本存储及查找功能

    散列表的工作原理是通过哈希函数将关键字映射到一个固定大小的数组中。哈希函数的目标是使得不同的关键字能够均匀地分布在整个数组中,以避免或减少冲突。在电话本的例子中,关键字可能是联系人的姓名,而存储的信息...

    Data_Structure的源代码

    7. **散列表(哈希表)**:散列表通过哈希函数将键映射到数组的索引上,实现快速查找、插入和删除。C++标准库没有内置的散列表,但可以使用`std::unordered_map`或`std::unordered_set`作为替代。 8. **排序算法**...

    数据结构c++实现方法

    7. **散列表**(哈希表):散列表通过哈希函数将键映射到数组索引,实现快速查找。C++标准库的`std::unordered_map`和`std::unordered_set`是实现散列表的例子。理解哈希冲突及其解决方法是关键。 8. **堆**:堆是...

    数据结构的c++伪码实现

    散列表(哈希表)提供了一种快速查找的方法,通过散列函数将键映射到数组索引。理想的散列函数可以使得键的分布均匀,减少冲突。解决冲突的方法有开放寻址法和链地址法。C++ STL中的`unordered_map`和`unordered_set...

    《数据结构——C++实现》(第二版)课本源代码.zip

    5. **散列表(哈希表)**:通过哈希函数将元素映射到一个固定大小的数组中,提供快速的查找、插入和删除操作。C++标准库没有直接提供哈希表,但可以使用第三方库如`boost::unordered_map`。 6. **树**:包括二叉树...

    数据结构及源码

    7. **散列表**(哈希表):散列表通过散列函数将键映射到数组的索引,实现快速查找。C++标准库中的`std::unordered_map`和`std::unordered_set`提供了散列表功能。 8. **排序算法**:包括冒泡排序、选择排序、插入...

    数据结构(C++)课件

    散列表是一种通过哈希函数将键映射到数组索引的数据结构,提供近乎常数时间的查找、插入和删除操作。C++的unordered_map和unordered_set是实现散列表的工具。 六、排序与查找算法 数据结构课程会讲解多种排序算法,...

    《java数据结构》源码及课后答案

    散列表通过散列函数将键映射到数组的索引,实现快速查找。Java中的HashMap和LinkedHashMap类是散列表的典型应用,它们提供了O(1)的平均时间复杂度来执行插入、删除和查找操作。 七、树 树是一种非线性的数据结构,...

    VC中数据结构与算法

    首先,我们要了解数据结构的基础,包括数组、链表、栈、队列、散列表(哈希表)和树。数组是最基础的数据结构,允许我们以固定大小和顺序存储元素。链表则提供了更灵活的内存管理,每个节点包含数据和指向下一个节点...

    C++数据结构代码实现.zip

    8. **散列表(哈希表)**:散列表通过散列函数将键映射到数组索引,提供快速的查找、插入和删除操作。C++标准库中的`std::unordered_map`和`std::unordered_set`实现了散列表。 9. **堆**:堆是一种特殊的树形数据...

    C++写的数据结构算法源码,很详细的

    7. 散列表(哈希表):散列表提供快速的查找、插入和删除操作,通过散列函数将键映射到数组的特定位置。C++标准库中的`std::unordered_map`和`std::unordered_set`实现了散列表。 二、算法 1. 排序算法:包括冒泡...

    数据结构 C++ 语言描述

    8. **散列表**(哈希表):散列表提供快速的插入、删除和查找操作,通过哈希函数将键映射到数组索引。C++标准库的`std::unordered_map`和`std::unordered_set`实现了哈希表。 9. **排序算法**:C++提供了多种排序...

    数据结构的一些例子(C++)

    7. **散列表(哈希表)**:散列表提供快速的插入、删除和查找操作,通过哈希函数将键映射到数组索引。C++标准库的`std::unordered_map`和`std::unordered_set`提供了哈希表实现。 8. **堆**:堆是一种特殊的树形...

    数据结构李根强

    李根强的《数据结构(C++版)(第二版)》涵盖了这些基本和高级的数据结构,包括数组、链表、栈、队列、散列表、树(二叉树、平衡树如AVL树和红黑树)、图、堆和排序算法等。这些内容不仅涉及理论,还强调实际应用,...

    数据结构实验(c++)源代码

    8. **散列表(哈希表)**:散列表通过散列函数将键映射到数组索引,提供快速的插入、删除和查找操作。C++标准库中的`&lt;unordered_map&gt;`和`&lt;unordered_set&gt;`容器实现了散列表。 9. **排序算法**:包括冒泡排序、选择...

    Java数据结构与算法

    而HashMap是基于散列表实现的映射,提供了快速的键值对存取。 此外,高级主题如图论和树结构也是Java数据结构与算法中的重要部分。树包括二叉树、平衡树(如AVL树和红黑树)、堆(如最大堆和最小堆),它们在数据...

    数据结构算法与应用-C++语言描述

    4. 散列表(哈希表):提供快速的查找和插入操作,通过散列函数将数据映射到固定大小的数组中,是实现关联数组和数据库索引的常用方法。 5. 排序与搜索算法:冒泡排序、选择排序、插入排序、快速排序、归并排序、二...

    C++描述的数据结构

    4. 散列表(哈希表) - 散列表是一种通过哈希函数快速定位数据的数据结构,提供近似常数时间的查找、插入和删除操作。C++标准库中的`std::unordered_map`和`std::unordered_set`实现了散列表。 5. 排序和搜索 - ...

    数据结构实习,数据结构实训,C,C++源码.zip

    6. **散列表(哈希表)**:散列表提供快速查找功能,通过哈希函数将键映射到数组索引。C++标准库中的`std::unordered_map`和`std::unordered_set`实现了哈希表。 7. **堆**:堆是一种部分有序的树形数据结构,通常...

    数据结构所有源代码(c++)自己写得

    7. **散列表**(哈希表):散列表提供快速的查找、插入和删除操作,通过哈希函数将键映射到数组的索引。C++的STL提供了`unordered_map`和`unordered_set`容器来实现散列表。 8. **堆**:堆是一种部分有序的树形数据...

Global site tag (gtag.js) - Google Analytics