Почему слайс Go нельзя использовать в качестве ключей на картах Go почти так же, как массивы можно использовать в качестве ключей?

Question

Почему срез Go (который является реализацией массивов Go) не может использоваться в качестве ключей в картах Go почти так же, как массивы могут использоваться в качестве ключей?

Answer 1

Вот ответ Найджела Тао из https://groups.google.com/forum/:

Одна из причин заключается в том, что массивы являются типами значений. Если a0 является [N]int (массив) затем делает

a1 := a0
a1[0] = 0

не повлияет a0[0] совсем.

Для сравнения, срезы ссылаются на базовый массив. Копирование значения фрагмента - O(1) вместо O (длина). Если s0 является []int (кусочек) затем делает

s1 := s0
s1[0] = 0

повлияет на то, что s0[0] является.

http://play.golang.org/p/TVkntIsLo8

Ключи карты нуждаются в некотором понятии равенства. Для массивов это просто поэлементное равенство. Для срезов существует несколько способов определения равенства: один является поэлементным равенством, другой ссылается на то же хранилище массива. Кроме того, нужно ли для вставки карты создавать (дорогую) копию всего резервного массива? Копирование, вероятно, было бы менее удивительным, но оно несовместимо с тем, что делает назначение.

Что должен печатать этот фрагмент кода?

m := make(map[[]int]bool)
s0 := []int{6, 7, 8}
s1 := []int{6, 7, 8}
s2 := s0
m[s0] = true
s2[0] = 9
println(m[s0])
println(m[s1])
println(m[s2])

Разные программисты могут иметь разные ожидания. Чтобы избежать путаницы, мы просто решили пока не разрешать использование слайсов в качестве ключей карты.

Answer 2

Чтобы ответить на точное "почему не могу?":

Spec: Типы карт:

Операторы сравнения == и!= Должны быть полностью определены для операндов типа ключа; таким образом, тип ключа не должен быть функцией, картой или срезом.

Спецификация не допускает ключевые типы, где сравнение не определено. Spec: операторы сравнения также подтверждают это:

Значениясреза, карты и функции не сравнимы.

Для рассуждений см. Ответ Смаркса (который цитирует ответ Найджела Тао). И читать дальше.

Карта Go использует реализацию hashmap. В общем случае (независимо от языка программирования) изменение значения, используемого в качестве ключа в хэш-карте, может привести к неопределенному (или неожиданному наименьшему) поведению. Обычно хеш-код ключа используется для обозначения сегмента, в который помещается значение (пара ключ-значение). Если ключ изменяется, и вы запрашиваете связанное значение для этого ключа, реализация может искать в неправильном сегменте (и, следовательно, сообщать, что не может его найти), потому что измененное значение ключа, скорее всего, дает другой хэш-код, который может обозначать другое ведро.

В Go срезы являются просто дескрипторами для непрерывной части базового массива, и присвоение значений срезов только копирует эти дескрипторы. Таким образом, используя срез в качестве ключа, можно ожидать, что реализация карты копирует только этот заголовок среза (который является указателем на первый ссылочный элемент в базовом массиве, длину и емкость). Это сработало бы, только если хэш-вычисление и равенство использовали бы эти 3 элемента и ничего больше, но для нас (людей, программистов) срез означает элементы, к которым можно получить доступ через заголовок среза, которые также могут быть изменены (вызывая проблемы, описанные выше).

Если карта позволяет срезу в качестве ключей функционировать должным образом, она должна будет обновлять свое внутреннее состояние и структуру данных всякий раз, когда изменяется элемент среза любого среза (который используется в качестве ключа), чего не следует ожидать.

Массивы хороши в этом отношении: массив означает все его элементы; Копирование массива копирует все элементы, и сравнение определяется так:

Значения массива сравнимы, если значения типа элемента массива сравнимы. Два значения массива равны, если их соответствующие элементы равны.

И если вы измените элемент массива, который вы использовали в качестве ключа ранее: не проблема, поскольку новый массив (с этим измененным элементом) не равен оригиналу, который хранится и используется на карте, поэтому запрашивает соответствующее значение с измененным массивом не даст никаких результатов, а запрос с неизмененным исходным массивом вернет вам ранее сохраненное значение.