The LinkedHashMap's Remove is O(n) ? #120

New issue

Closed

opened 2019-09-05 05:38:02 +00:00 by wxiaoguang · 1 comment

wxiaoguang commented

2019-09-05 05:38:02 +00:00

(Migrated from github.com)

The LinkedHashMap's Remove is O(n) ?

// Remove removes the element from the map by key.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (m *Map) Remove(key interface{}) {
	if _, contains := m.table[key]; contains {
		delete(m.table, key)
		index := m.ordering.IndexOf(key)   // FIXME: O(n) here ?
		m.ordering.Remove(index)
	}
}

The LinkedHashMap's `Remove` is O(n) ? ``` // Remove removes the element from the map by key. // Key should adhere to the comparator's type assertion, otherwise method panics. func (m *Map) Remove(key interface{}) { if _, contains := m.table[key]; contains { delete(m.table, key) index := m.ordering.IndexOf(key) // FIXME: O(n) here ? m.ordering.Remove(index) } } ```

emirpasic commented

2019-09-05 13:31:55 +00:00

(Migrated from github.com)

Indeed, you are right. I should note that in documentation perhaps to be clear on that.

As the name suggests, the underlying structure to hold keys is a linked list in order to have the keys in the insertion order. Somebody requested this, so I've implemented it.

One could, however, implement a reversed lookup for this to find the index with O(1), but that would add more memory usage to the structure. If you feel like that's a good compromise in terms of performance vs memory, that I could change that or you can feel three to change it.

Indeed, you are right. I should note that in documentation perhaps to be clear on that. As the name suggests, the underlying structure to hold keys is a linked list in order to have the keys in the insertion order. Somebody requested this, so I've implemented it. One could, however, implement a reversed lookup for this to find the index with O(1), but that would add more memory usage to the structure. If you feel like that's a good compromise in terms of performance vs memory, that I could change that or you can feel three to change it.