最佳邻接表实现

Question

我可以将邻接列表实现为链表数组或链表映射(即。一张哈希表)。是否有理由在Map实现之上使用Array实现？我之所以问这个问题，是因为我遇到过许多描述Array实现的网站，但很少有人提到使用哈希表。据我所知，HashTables的性能应该优于数组。

下面是我如何编码基于哈希表的邻接列表以及助手类的相关代码。

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

是否有理由在地图实现之上使用数组实现？

是：

• 当您知道图中的节点数为n，而
• 则由0..n-1

范围内的整数标识

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

注意:如果用数组(和push)替换链接列表，肯定会更快。