• 第五章 散列表
  • 散列函数：
  • 使用：
  • 冲突
  • 性能关键
  • 小结
• 第六章 广度优先搜索
  • 图
  • 广度优先
  • 队列
  • 问题
  • 运行时间

散列表。广度优先搜索。

第五章 散列表

js中的对象是基于散列表结构的。

散列函数：

1. 相同的输入映射到相同的索引。
2. 不同的输入映射到不同的索引（冲突时会存在相同索引，当时有其他方法解决冲突）。
3. 知道数组大小，不返回无效索引。

使用：

1. 查找。
2. 去重，将值作为key存在散列表中，做已存在判断，js中要注意判断key类型，最好做temp[key][typeof key]的处理。
3. 缓存，其实还是查找的问题，做选择存储，遇到缓存内容直接返回。

冲突

数组不可能无限长，生成的索引相同会产生冲突。

解决方法

1. 拉链法，索引存链表，链表中存键和值和next。同时又有一个问题，散列函数的重要性，应将所有的键均匀映射。
2. 拉链法变种，不存链表，存树或hash表。
3. 开放寻址，冲突则找下一个不冲突的位置，在满容后会进行扩容。

性能关键

1. 较低的装载因子。
2. 良好的散列函数。

装载因子：散列表包含的元素数比位置总数。比如，恰好占满则为1，使用一半则为0.5。 散列表调整长度的成本是比较大的，先建立新的数组，再将原有元素插入新的散列表。

• SHA函数————好的散列函数。

小结

• 你可以结合散列函数和数组来创建散列表
• 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
• 散列表的查找、插入和删除速度都非常快。
• 散列表适合用于模拟映射关系。
• 一旦装填因子超过0.7，就该调整散列表的长度。
• 散列表可用于缓存数据。
• 散列表非常适合用于防止重复。

第六章 广度优先搜索

图

这就是个最基本的图了，节点+边

○--->○

图根据有没有箭头分为有向图和无向图，其中无向图是即双向关系的图。 整个图中只有单向指向关系的图又可叫树这句话是错的，每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

广度优先

按层遍历，遍历完第一层关系后进行第二层的遍历。实际操作时，可先将根节点添加至队列，检测根节点，如不是目标值，移出根节点，再将根节点的子节点（所指向的节点）添加至队列，循环直到找到目标值。

let third1 = {
  name: 'third1'
}
let second1 = {
  name: 'second1',
  member: [third1]
}
let second2 = {
  name: 'second2',
  member: [third1]
}
let first = {
  name: 'first',
  member: [second1, second2]
}

function read(obj) {
  let pool = [obj];
  for(let i = 0; i < pool.length;i++){
    console.log(pool[i]);
    // 有子项则将子项加入pool
    // 如此走完第一层就会走第二层
    if (pool[i].member) {
      pool = pool.concat(pool[i].member)
    }
  }
}
read(first)

可以解决两个问题：

1. 有没有到达目标的路径？
2. 到达目标的最短(边最少)路径是？

队列

我们把上面的concat改成使用shift取出第一项和push操作添加，即删除第一项，向末尾添加项，即是使用队列做数据存储，先进先出。

问题

运行上面的代码会发现一个问题，third1被输出了两次，所以我们需要对已检查过的项添加标记，这样也能避免两个相互指向导致的死循环问题。

运行时间

O(V + E) V:顶点数 E:边数
对每个顶点要做添加到队列操作为O(V)
对每条边都要进行前进操作O(E)