Java实现LRU算法（哈希表加双向链表）

LRULRU 全称 Least Recently Used，意为最近最少使用，是最常见的页面置换算法，也常用于实现缓存淘汰策略。实现哈希表 + 双向链表。链表头节点代表最近使用过的数据。对于 get 操作，首先判断 key 是否存在：如果 key 不存在，则返回 -1；如果 key 存在，则 key

查看全文

布隆过滤器

布隆过滤器布隆过滤器（Bloom Filter）是一种来检索元素是否在给定大集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。它由位数组和一系列哈希函数构成。初始时位数组的值全为0。布隆过滤器原理加

查看全文

基数排序、堆排序分析与实现（Java）

基数排序基数排序（Radix Sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort），顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定的排序，其时间复杂度为O (nlog(r)m)，其中

查看全文

归并排序、快速排序、希尔排序分析与实现（Java）

归并排序归并排序归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归

查看全文

二分查找、插值查找、斐波那契（黄金分割）查找分析与实现（Java）

二分查找  二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。基本思想  首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录

查看全文