从数组到 HashMap 之算法解释

文章预览

长按图片识别二维码报名参与码云用户见面交流会 一、数组是什么？ 忘了在哪本书里曾看到过类似这样的一句话“所有的数据结构都是数组的演化”，想想其实是有道理的，因为计算机的内存其实就是线性的存储空间。 Java示例代码：int[] array = new int[5] 忽略对象头信息和数组长度信息，JVM执行时会在堆中分配20个字节的内存空间，看起来就是这样的： 这样的数据结构可以很方便地通过数组下标存取数据，但在查找时需要遍历数组，平均时间复杂度为O(n/2)。 当数据量很大或者查找操作频繁的时候，这样的遍历操作几乎是不可接受的。那么，如何才能够在更短的时间内快速找到数据呢？   二、二分查找 假如数组内的元素是已经排序的，那么很自然的方式就是使用 ………………………………