变量和类型 - 对象的底层数据结构

[logan70]

对象的底层数据结构

JavaScript中的对象是基于哈希表结构的。

哈希表（Hash table）、哈希函数（Hash Function）与哈希碰撞（Hash Collision）

哈希表 又称散列表，根据键直接访问在内存存储位置的数据结构。通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。

哈希函数 又称散列函数、散列算法，上述映射函数即为哈希函数，是一个表示键和内存存储值位置的映射关系的函数。常见的构造哈希函数的方法有直接定址法、除留余数法、随机数法等。

哈希碰撞 又称哈希冲突，指不同键经过哈希函数计算后得到相同哈希地址的情况。具有相同函数值的关键字对该哈希函数来说称做同义词。

处理哈希碰撞

开放定址法

当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1...，直到找出不冲突的哈希地址pi，将相应元素存入其中。

优点：储空间更加紧凑，利用率高。
缺点：冲突元素间产生关联，无法直接删除，会破坏寻址链，只能在删除节点上作删除标记。

拉链法

又称链地址法，将散列到同一个存储位置的所有元素保存在一个链表中。

优点：处理冲突简单，非同义词决不会发生冲突，因此平均查找长度较短。
缺点：指针需要额外的空间，降低构建哈希表时的效率。

查找效率

• 二分查找： 复杂度为O(log2n)，但只能用于有序列表。
• 遍历查找： 复杂度为O(n)。
• 哈希表： 理想的哈希函数实现的哈希表，对其任意元素的查找速度始终为常数级，即O(1)。

如果遭到恶意哈希碰撞攻击，拉链法会导致哈希表退化为链表，即所有元素都被存储在同一个节点的链表中，此时哈希表的查找速度=链表遍历查找速度=O(n)。