标签: 算法

算法分析点到

算法分析的逻辑线条比如自然科学中的经典方法:通过观察或实验收集数据;抽象简化的假设性模型;基于模型预测未来;通过实验数据核实并校准分析模型。这方面耳熟能详的先例有:牛顿爵士推演得来的万有引力定律仰赖于第谷、开普勒的数据;借助万有引力定律,科学家后来成功预测了海王星的存在。简单地说,这种经典方法在定性和定量分析中往复折返,基于定性分析推断第一、第二自变量,基于定量分析明确因变量和自变量的关系(甚或将

符号表与二叉查找树

符号表符号表用于存储键值对。通常符号表按功能提供了如下 API(由 API 可逐步深入到设计决策、测试用例、实现等): get: 获取指定 key 键的值。 put: 将键值对存入符号表中。 delete: 删除指定的键值对。 contains: 判断符号表中是否包含指定的键。 isEmpty: 判断符号表是否为空。 size: 获取符号表中键值对的数量。 keys: 获取符号表中所有 key

透过散列表看HashMap

散列表用于存储键值对。先举两个例子:如果使用有序数组存储键值对,那么当存在某个较大的键时,整个数组所占用的内存空间就会很大;如果使用无序数组存储键值对,那么在查找元素时就需要遍历数组项,造成了性能的低效。与这两个例子不同的是,散列表有效地平衡了时间和空间复杂度。创建散列表的流程分为: 通过散列函数将键转化为散列码,以作为数组的索引。 通过碰撞处理解决两个或多个散列码等值的情况。 散列函数制作散

HashMap中的红黑树

HashMap 预期以链表数组的形式存储数据,即以 key 键的散列码计算索引,然后将元素插入到作为数组项的链表中(每个数组项称为桶)。为了提升查询的效率,HashMap 中存在一个阈值,当桶中的元素量超过这个阈值时,桶的数据结构就会从链表转变成红黑树。与红宝书中基于 2-3 树实现的红黑树不同,HashMap 中的红黑树基于 2-3-4 树实现。补充说明的是,Java 中的 TreeMap 也是

红黑树

与数组相比,链表提升了插入元素的效率。因为数组在插入元素时,需要移动后续元素的位置;而链表只需要改变后继元素的 prev 属性。然而在查询元素时,链表需要遍历所有元素,并不高效。借助于红黑树,既能提升查询的效率,又能保证插入的效率。 为什么说红黑树有助于提升查询和插入的效率呢?因为红黑树本质上是一棵完美平衡的二叉查找树,可以通过节点的有序性保证查找和插入操作的便捷,其作时间复杂度就是树的高度 O(