asp.net做网站原理,网站建设落地页,男女直接做的视频视频网站,建设工程造价网在定期检查JDK中是否存在一种或另一种标准算法时#xff0c;我决定进行这种索引。 有趣的是#xff0c;为什么其中包含一些著名的数据结构或算法#xff0c;而另一些却没有#xff1f; 此调查的格式仅涉及JDK的算法和数据结构的关键特性和功能#xff0c;所有详细信息和完… 在定期检查JDK中是否存在一种或另一种标准算法时我决定进行这种索引。 有趣的是为什么其中包含一些著名的数据结构或算法而另一些却没有 此调查的格式仅涉及JDK的算法和数据结构的关键特性和功能所有详细信息和完整描述-您可以在javadoc或jdk源代码中轻松找到。 让我们从简单开始到复杂 JDK的数据结构 堆 jdk中有一个堆栈 它是从堆栈中出现的-类Stack 但不建议使用它它很复杂又很奇怪它继承自Vector 因此基于Dynamic Array并已同步。 为什么一个简单的栈需要这一切为什么它不只是一个接口-目前尚不清楚讨论过很多次 1 2 但似乎只是一个架构的错误同样与载体本身。 顺便说一句JDK作者自己建议使用Deque 。 Deque – 双端队列的接口apiO中的LIFO FIFO1其中包括堆栈操作pushpopisEmptysize并且到目前为止在jdk中可用1.6 。 当然将这些堆栈操作放在接口Stack中会更合乎逻辑例如让Deque继承它但是由于Stack已经存在并且向后兼容性是Java的“圣杯” –他们不得不牺牲常规设计。 Deque的实现是ArrayDeque和LinkedList 它们也是常规队列的实现者–因此我们将在后面讨论。 队列 接下来让我们看一下队列数据类型 。 这里的一切都很好设计得很好。 队列 – FIFO队列的接口api以恒定时间O1添加到开头并从结尾删除。 主要实现有 ArrayDeque 基于动态可扩展数组的循环缓冲区 填充时加倍和LinkedList 经典的双向链接列表 大小不受限制。 令人惊讶的是第一个不支持随机访问 使用索引添加/删除/获取第二个却支持On时间并通过链表进行迭代。 这些类还实现了上述Deque因此它们支持从末尾移除并在恒定时间内添加到顶部。 接下来从jdk 1.5开始添加了PriorityQueue 这实际上违反了合同因为队列元素不是从末尾检索的并且也不添加到头部而是根据优先级检索的。 PriorityQueue基于可扩展的二进制堆 其顶部最小根据其比较器并且在填充时提高了1.5倍。 关键特征分别是元素的添加/删除在Olog N中而对最小值标头的引用在O1中。 其他类型的队列是为多线程使用而设计的它们是 BlockingQueue TransferQueue ConcurrentLinkedQueue和ConcurrentLinkedDeque 。 BlockingQueue ArrayBlockingQueue LinkedBlockingQueue PriorityBlockingQueue 的实现是其原始版本的一种同步版本即几乎每个操作都是串行执行的具有独占锁定。 对于DelayQueue也是如此也是同步的并且在内部使用PriorityQueue 。 其他实现 SynchronousQueue TransferQueue LinkedTransferQueue ConcurrentLinkedQueue ConcurrentLinkedDeque –基于不同的方法它们使用基于链表和CAS指令的非阻塞队列算法这些算法在多处理器环境中可以很好地并行化。 详细描述在源代码中。 这类算法的理论是一个非常庞大且现代的话题因此还没有很好的标准化和结构化它们超出了本文的讨论范围也不属于另一篇文章的主题。 优先队列 就像从jdk 1.5开始所说的那样有一个通用的PriorityQueue根据元素比较器工作。 而且jdk中还有堆的另一种实现。 这是很好的旧Timer 它是内部类– TaskQueue顶部的延迟最小的任务。 当然这是一个私有类除了在Timer内部不能使用。 清单 如您所知有顺序和/或随机访问类型列表。 在Java中它是List 主要有2种实现首先-是ArrayList 支持随机访问 基于动态可扩展数组 填充时增加一半但是在删除所有元素后不会缩小您需要调用a特殊方法 trimToSize 。 第二个-再次是LinkedList它是一个双链表顺序访问大小仅受jvm的内存限制。 尽管也存在随机访问索引的方法–如前所述它们需要On时间。 因此java集合中没有最简单的链表实现尽管这是一个好主意链接的开销减少了2倍并且没有简单的堆栈。 要在多线程环境中使用列表有几个选项 CopyOnWriteArrayList 更改操作– On包装器 synchonizedList 以及过时的Vector 。 符号表 它们在JDK中显示为二进制树和哈希表。 二叉树 –它是TreeMap 或TreeSet SortedMap 也是SortedSet的实现它基于经典的红黑树 即是平衡的并且对于Olog N保证了其基本操作并且不限大小。 jdk中不存在其他类型的树。 哈希表是HashMap 也是HashSet 它可能是Java中最常用的结构它基于可动态扩展的哈希表具有与链表的单独链接 具有所有功能性能取决于哈希函数的质量因此最坏的情况是ON。 当大小达到预定的loadFactor时 HashMap的大小将增加一倍。 值得注意的是为了保护错误的哈希函数使用了双哈希并且对调用hashCode的结果应用了棘手的位算法。 在JDK中也有带有开放地址线性探测的哈希表实现。 其中之一是IdentityHashMap 当键和值都存储在彼此相邻的同一数组中时它会使用经典线性探测的优化版本以实现更好的数据缓存javadoc«大型表的局部性比使用单独的数组» 第二种开放寻址实现是非常特定的它仅用于存储ThreadLocal元素 ThreadLocalMap中的内部隐藏类当然不可用。 还有多线程版本 ConcurrentHashMap中 包装synchronizedMap 哈希表和ConcurrentSkipListMap 。 包装器-自然只是阻止了常规HashMap Hashtable的版本-同一件事并且是旧的不建议使用 ConcurrentHashMap-锁条版本减少了关键的锁部分最好阅读JCiP 这里是 摘录 ConcurrentSkipListMap –是哈希表的非阻塞命名算法的改编版本有关详细信息请参见源代码。 集合不包含重复项–在Java中设置 并通过HashMap实现因此所有被称为哈希表的对象–对HashSet有效。 图表 图结构和算法未在jdk中表示。 因此您只能为此使用第三方库。 弦乐 java中通常有一个字符串实现基于unicode字符数组。 值得一提的是从1.7_17版本开始由于已复制子字符串因此子字符串的性能为On。 有趣的是 此实现使用了一种简单的强力子字符串搜索算法该算法在最坏的情况下以ON * M运行并且没有一些有效的算法在有限状态机上构建Knuth-Morris-Pratt等 。 原因有几个字母UTF字符大〜65K因此存储状态机的开销很大而就采用了蛮力算法不使用额外的内存。 其次在平均输入字符串上–根据统计数据该算法与其他算法相比并没有很多。 与排序相同有有效的基数排序字符串algsLSDMSD等但是在jdk中有一个用于字符串的标准对象排序 如果运行则以OM * N * log N运行大部分线相差不大M –线长。 原因是相同的快速计数字符串算法需要额外的UTF字母大小的数组这使得它们在平均输入上非常无效。 JDK算法 排序 由于jdk7发生了许多有关各种选项的更改因此讨论了很多次关于此主题的信息和文章很多您可以轻松地将其搜索出来。 简而言之这是jdk中排序实现的实际列表 TimSort –默认情况下对对象进行排序 mergesort –还用于对象旧版本通过系统属性启用 Dual-Pivot Quick sort –用于基元然后按计数排序用于字节/字符数组最后插入排序用于任何情况下使用的小数组。 集合内容使用Collections.sortList…进行排序仍然可以通过将集合复制到数组中对其进行排序然后相应地覆盖集合内容来完成。 因此尽管没有开销对集合进行排序仍然是不可能的尽管我认为拥有就地排序的链表是一个好主意。 Java中的字符串排序也使用对象版本完成原因已经提到。 正在搜寻 对于原语和对象的所有数组以及随机访问列表实现例如ArrayList等都存在传统的二进制搜索 。 此外JDK中还有一个二进制搜索链接列表的版本 令人惊讶的是JDK没有对链表进行排序但是对它们进行二进制搜索 尽管没有太大意义因为这种版本的性能为ON。 常用表达 为此提供了Pattern和Matcher类。 Java使用基于带回溯的非确定性有限状态机 NFA 的传统实现。 因此在退化的输入上在最坏的情况下它给出了指数复杂度 Om ^ N例如在Java中运行此regexp并尝试添加/删除“ a”符号“ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.aa * b” 此外还有所谓的有序交替-此功能可在找到第一个匹配项后停止搜索但不会显示最具体最长的搜索结果 例如 。 哈希函数校验和 jdk中有hashCode实现的六个版本并且Park-Miller_random_number_generator是默认版本其他很简单例如常量或对象内存地址并且不使用算法您可以在c jdk源代码中找到它们。 MessageDigest类中还有行业标准的哈希算法SHA-*MD5和变体。 对于校验和有Adler-32 javadoc 和CRC32 javadoc 算法的实现。 压缩 jdk中有一个标准的压缩deflate Deflater 算法的实现并且zip / gzip jdk utils使用它。 它们都在java.util.zip包中 。 摘要 如您所见经典数据结构并未完全用Java呈现但与此同时几乎所有jdk中的所有数据结构都可以使用很多线程安全版本。 缺少的是一个悬而未决的问题。 例如您可以争辩jdk是否需要一些Union-Find但是在社交网络时代完全缺少该语言的图形结构和算法非常令人惊讶并且实际上会产生许多错误和自行车。 参考来自我们JCG合作伙伴 Mikhail Baturov 的JDK 7的算法和数据结构这是另一个俄罗斯编程人员.blog博客。 翻译自: https://www.javacodegeeks.com/2013/07/algorithms-and-data-structures-of-jdk-7.html
