最佳邻接表实现

Question

我可以将邻接表实现为链表的 Array，或链表的 Map（即哈希 Table)。是否有理由在 Map 实现上使用 Array 实现？我问是因为我遇到过很多描述 Array 实现的网站，但很少提到使用 Hash Tables。据我了解，HashTables 应该优于 Arrays.

下面是我将如何编写基于哈希 Table 的邻接列表以及助手类.

的相关代码

LinkedListNode.js

class LinkedListNode {
  constructor(value = 0, next = undefined) {
    this.value = value;
    this.next = next;
  }
}

LinkedList.js（删除了不必要的功能）

class LinkedList {
  constructor(headValue = null) {
    this.head = headValue ? new LinkedListNode(headValue) : headValue;
  }

  addToTail(value) {
    const node = new LinkedListNode(value);
    if (!this.head) {
      this.head = node;
    } else {
      let pointer = this.head;
      while (pointer.next) {
        pointer = pointer.next;
      }
      pointer.next = node;
    }
  }
  
  toArray() {
    const items = [];
    let pointer = this.head;
    while (pointer) {
      items.push(pointer.value);
      pointer = pointer.next;
    }
    return items;
  }
}

HashTable.js - 我们假设没有碰撞

class HashTable {
  constructor() {
    this.items = {};
  }

  set(key, value) {
    if (this.items[key]) {
      this.items[key].addToTail(value);
    } else {
      this.items[key] = new LinkedList(value);
    }
  };

  get(key) {
    return this.items[key]; 
  }

  print() {
    const entries = Object.entries(this.items);
    for (let i = 0; i < entries.length; i += 1) {
      const [key, list] = entries[i];
      console.log(`${key}: ${list.toArray()}`);
    }
  }
}

用法

const adjacencyList = new HashTable();
adjacencyList.set(1, 2);
adjacencyList.set(2, 4);
adjacencyList.set(3, 1);
adjacencyList.set(3, 2);
adjacencyList.set(3, 5);
adjacencyList.set(4, 6);
adjacencyList.set(5, 2);
adjacencyList.set(5, 4);
adjacencyList.set(5, 6);
adjacencyList.set(6, null);
adjacencyList.print();

// Outputs
'1: 2'
'2: 4'
'3: 1,2,5'
'4: 6'
'5: 2,4,6'
'6: '

Answer 1

Is there ever a reason to use the Array implementation over the Map implementation?

是：

当你知道你的图有 n 个节点数，并且
节点由 0..n-1

在这种情况下，“散列”是数组中的索引。当您使用数组而不是普通对象时，某些 JavaScript 引擎可能会生成更快的代码。

注意：如果将链表替换为数组（和push）肯定会更快。

最佳邻接表实现

Best Adjacency List Implementation

javascript

hashtable

graph

hashmap

adjacency-list