Web高级 JavaScript中的数据结构

概述复杂度分析 大O复杂度表示法 常见的有O(1), O(n), O(logn), O(nlogn) 时间复杂度除了大O表示法外,还有以下情况 最好情况时间复杂度 最坏情况时间复杂度 平均情况时间复杂度 均摊时间复杂度 代码执行效率分析 大多数情况下,代码执行的效率可以采用时间复杂度分析,但是大O表示法通常会省略常数。 但是在工业级实现中，真正的执行效率通常会考虑多方面： 时间复杂度 空间复杂度 缓存 复杂度分析 大O复杂度表示法
常见的有O(1),O(n),O(logn),O(nlogn)
时间复杂度除了大O表示法外,还有以下情况 最好情况时间复杂度 最坏情况时间复杂度 平均情况时间复杂度 均摊时间复杂度 代码执行效率分析

大多数情况下,代码执行的效率可以采用时间复杂度分析,但是大O表示法通常会省略常数。
但是在工业级实现中，真正的执行效率通常会考虑多方面：

时间复杂度 空间复杂度 缓存友好 指令条数 性能退化(如哈希冲突解决方案等) 等

以上是理论层级,对于前端开发来说,如果你开发的是基础库会被广泛使用时,只是基于理论的分析是不够的。
此时就可以借助一些基准库来对你的模块进行测试: benchmark.js

数据结构 1. 数组 特点: 连续内存,支持下标访问,缓存友好,时间复杂度O(1)
深入: 从Js继承链可以知道在Js中的Array数组继承于Object,在某些情况下数组会退化为哈希表结构[Dictionary]。
思考: 考虑如下情况,浏览器会怎样存储该数组?

let myArray = [10000];myArray[0] = 0;myArray[9999] = 1;

2. 链表 特点: 非连续内存,查找元素时间复杂度最坏情况O(n),最好情况O(1)。
单向链表 双向链表 深入: 判断链表是否有环形?
使用一个步进为1,和一个额外的步进为2的参数,如果在遍历完之前相遇,则有环。 3. 栈 特点: 先进后出,后进先出,底层结构可以为数组或链表。
场景: 函数调用时对当前执行环境进行入栈 *** 作,调用完成后出栈恢复调用前上下文。
深入: 递归调用时连续入栈 *** 作,如果递归层级过深造成堆栈溢出。
比如AngularJs中的脏值检查嵌套深度上线为10。
思考: 浏览器的前进后退功能可否用栈实现？
使前进栈和后退栈的双栈结构 4. 队列 特点: 先进先出,底层结构可以为数组或链表。
无阻塞队列
基于链表 阻塞队列
基于数组的循环队列
深入: Js中的Macro队列和Micro队列 5. 跳表

底层为链表,为了增加查找效率,在链表基础上,以(2/3/4/../n)个节点增加一层查找链表

特点: ‘支持区间查找‘,支持动态数据结构,需要额外的存储空间来存储索引链节点 时间复杂度: 基于链表的查找时间复杂度由跳表层高决定

场景: 如Redis中的有序集合

6. 散列表 底层为数组结构，使用散列函数计算key将其映射到数组中的下标位置。
散列函数要求: 散列值为非负整数 key1 = key2,则 hash(key1) = hash(key2) key1 != key2,则 hash(key1) != hash(key2) 常见的哈希算法有: MD5,SHA,CRC等。 散列冲突： 开放寻址
线性探测：散列冲突时,依次往后查找空闲
双重散列: 使用多个散列函数,如果第一个散列值被占用,则用第二个散列值 链表法
散列冲突时,在一级数据后链接一个链表结构。该链表可以是单/双链,或树形链表 装载因子: 整个数组中已经被使用的位置/总位置 动态扩容: 当装载因子达到某个限定值(如:0.75)时，对整个底层数组进行扩容
注: 工业级实现中,动态扩容并不是一次完成的。
一次完成的动态扩容会造成性能瓶颈,一般是在装载因子达到设定值时,申请一个新的数组。在后续的每次 *** 作时,将一个数据从原数组搬到新数组，直到原数组为空。 JavaScript 对象数据结构 我在另一篇文章中有将到Js中的对象在底层存储的时候会有好几种模式，下面我们结合源码来详细分析一下

//https://github.com/v8/v8/blob/master/src/objects/Js-objects.h// 我们先来看Js中object的定义,继承自JsReceiver// line 278class JsObject : public JsReceiver {    //省略...}// line 26// 接下来再看,JsReceiver继承自HeapObject,并且有几个重要属性// JsReceiver includes types on which propertIEs can be defined,i.e.,// JsObject and JsProxy.class JsReceiver : public HeapObject { public:  NEVER_READ_ONLY_SPACE  // Returns true if there is no slow (IE,dictionary) backing store.  // 是否有快速属性模式  inline bool HasFastPropertIEs() const;  // Returns the propertIEs array backing store if it exists.   // Otherwise,returns an empty_property_array when there's a Smi (hash code) or an empty_fixed_array for a fast propertIEs map.  // 属性数组  inline PropertyArray property_array() const;  // Gets slow propertIEs for non-global objects.  // 字典属性  inline nameDictionary property_dictionary() const;  // Sets the propertIEs backing store and makes sure any existing hash is moved  // to the new propertIEs store. To clear out the propertIEs store,pass in the  // empty_fixed_array(),the hash will be maintained in this case as well.  voID SetPropertIEs(HeapObject propertIEs);  // There are five possible values for the propertIEs offset.  // 1) EmptyFixedArray/EmptyPropertyDictionary - This is the standard  // placeholder.  //  // 2) Smi - This is the hash code of the object.  //  // 3) PropertyArray - This is similar to a FixedArray but stores  // the hash code of the object in its length fIEld. This is a fast  // backing store.  //  // 4) nameDictionary - This is the dictionary-mode backing store.  //  // 4) GlobalDictionary - This is the backing store for the  // GlobalObject.  // 初始化属性  inline voID initialize_propertIEs();

由上可知对象有快速属性和字典属性两种模式，快速属性由数组存储，字典属性采用hash表存储。
快速属性这里不深入，我们接下来看看nameDictionary的底层结构

// https://github.com/v8/v8/blob/master/src/objects/dictionary.h// 我们先来看看继承链// line 202class V8_EXPORT_PRIVATE nameDictionary : public BasenameDictionary<nameDictionary,nameDictionaryShape>{}// line 128class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) BasenameDictionary : public Dictionary<Derived,Shape> {}// line 26class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Dictionary : public Hashtable<Derived,Shape> {}// 由上可知继承自Hashtable，我们来看Hashtable的定义// https://github.com/v8/v8/blob/master/src/objects/hash-table.h// 并且在文件开头的注释已经很详细了// Hashtable is a subclass of FixedArray that implements a hash table that uses open addressing and quadratic probing.*重要: hash表使用数组为基础数据,并在其上实现了开放寻址和二次探测// In order for the quadratic probing to work,elements that have not yet been used and elements that have been deleted are distinguished.  // Probing continues when deleted elements are encountered and stops when unused elements are encountered.* 为了使二次探测工作正常,未使用/被删除的元素将被标记删除而不是直接删除// - Elements with key == undefined have not been used yet.// - Elements with key == the_hole have been deleted.// 以下会被使用的hash表派生类// line 292template <typename Derived,typename Shape>class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) ObjectHashtableBase    : public Hashtable<Derived,Shape> {}接下来我们看看V8在实现hash表时的几个重要行为和参数// https://github.com/v8/v8/blob/master/src/objects/objects.cc1. 扩容// line 7590// 下面源代码是新增一个元素后的逻辑ObjectHashtableBase<Derived,Shape>::Put(Isolate* isolate,Handle<Derived> table,Handle<Object> key,Handle<Object> value,int32_t hash) {      int entry = table->FindEntry(roots,key,hash);  // Key is already in table,just overwrite value.  // key已经存在,覆盖值  if (entry != kNotFound) {    table->set(Derived::EntryTovalueIndex(entry),*value);    return table;  }  // 如果33%以上元素都被删除了,考虑重新hash  // Rehash if more than 33% of the entrIEs are deleted entrIEs.  // Todo(jochen): ConsIDer to shrink the fixed array in place.  if ((table->NumberOfDeletedElements() << 1) > table->NumberOfElements()) {    table->Rehash(roots);  }  // If we're out of luck,we dIDn't get a GC recently,and so rehashing isn't enough to avoID a crash.  // 如果没有足够的预估空位,按二倍大小进行重新hash  if (!table->HasSufficIEntCapacityToAdd(1)) {    int nof = table->NumberOfElements() + 1;    int capacity = ObjectHashtable::ComputeCapacity(nof * 2);    if (capacity > ObjectHashtable::kMaxCapacity) {      for (size_t i = 0; i < 2; ++i) {        isolate->heap()->CollectAllGarbage(            Heap::kNoGCFlags,GarbageCollectionReason::kFullHashtable);      }      table->Rehash(roots);    }  }// line 6583.// 下面是计算预估空位的逻辑Hashtable<Derived,Shape>::EnsureCapacity(Isolate* isolate,int n,AllocationType allocation) {  if (table->HasSufficIEntCapacityToAdd(n)) return table;  int capacity = table->Capacity();  int new_nof = table->NumberOfElements() + n;  const int kMinCapacityForPretenure = 256;  bool should_pretenure = allocation == AllocationType::kold ||                          ((capacity > kMinCapacityForPretenure) &&                           !Heap::InYoungGeneration(*table));  Handle<Derived> new_table = Hashtable::New(      isolate,new_nof,should_pretenure ? AllocationType::kold : AllocationType::kYoung);  table->Rehash(ReadonlyRoots(isolate),*new_table);  return new_table;}2. 收缩 // line 6622Hashtable<Derived,Shape>::Shrink(Isolate* isolate,int additionalCapacity) {  int capacity = table->Capacity();  int nof = table->NumberOfElements();  // Shrink to fit the number of elements if only a quarter of the capacity is filled with elements.  // 当只有1/4的装载量时,进行收缩  if (nof > (capacity >> 2)) return table;  // Allocate a new dictionary with room for at least the current number of  // elements + {additionalCapacity}. The allocation method will make sure that  // there is extra room in the dictionary for additions. Don't go lower than  // room for {kMinShrinkCapacity} elements.  int at_least_room_for = nof + additionalCapacity;  int new_capacity = ComputeCapacity(at_least_room_for);  if (new_capacity < Derived::kMinShrinkCapacity) return table;  if (new_capacity == capacity) return table;  const int kMinCapacityForPretenure = 256;  bool pretenure = (at_least_room_for > kMinCapacityForPretenure) &&                   !Heap::InYoungGeneration(*table);  Handle<Derived> new_table =      Hashtable::New(isolate,new_capacity,pretenure ? AllocationType::kold : AllocationType::kYoung,USE_CUSTOM_MINIMUM_CAPACITY);  table->Rehash(ReadonlyRoots(isolate),*new_table);  return new_table;}

总结

以上是内存溢出为你收集整理的Web高级 JavaScript中的数据结构全部内容，希望文章能够帮你解决Web高级 JavaScript中的数据结构所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。