Что происходит на аппаратном уровне при доступе к элементу массива?

Question

int arr [] = {69, 1, 12, 10, 20, 113}; 

Что происходит, когда я

int x = a[3]; 

????

Я всегда был под впечатлением, что a[3] имел в виду что-то вроде: «. Start по адресу памяти arr Walk 3 адреса памяти вперед Получить целое число, представленное по этому адресу памяти.»

Но тогда я смущен тем, как работают хеш-таблицы. Потому что, если хеш-таблицы реализованы как массив «ведер» (как говорит профессор в этой лекции: https://www.youtube.com/watch?v=UPo-M8bzRrc), вам все равно нужно подойти к ведерке, в которой вы нуждаетесь; следовательно, они не более эффективны для доступа, чем массив.

Может кто-нибудь прояснить это для меня?

Answer 1

Представьте память как большой, стол две колонки:

+---------+-------+ 
| ADDRESS | VALUE | 
+---------+-------+ 
|  ... | ... | 
+---------+-------+ 
|  100 | 69 | <-- &arr[0] is 100 
+---------+-------+ 
|  101 |  1 | 
+---------+-------+ 
|  102 | 12 | 
+---------+-------+ 
|  103 | 10 | <-- &arr[3] is 103 
+---------+-------+ 
|  104 | 20 | 
+---------+-------+ 
|  105 | 113 | 
+---------+-------+ 
|  ... | ... | 
+---------+-------+ 

Я хочу подчеркнуть, что это высоко упрощенная модель, но это должно дать вам представление о том, что происходит. Ваш компьютер знает, что ваш массив начинается, допустим, адрес 100.И поскольку все элементы в заданном массиве имеют одинаковый размер, вы можете легко получить доступ к третьему элементу массива, добавив +3 к начальному адресу. Компьютер не должен «ходить» к третьему элементу массива, он просто захватывает значение, которое хранится в памяти по адресу 100 + 3.

Если вы хотите увидеть пример этого в действии, скомпилировать и запустить следующий код:

#include <iostream> 
using namespace std; 

int main() { 
    int a[] = { 1, 2, 3 }; 
    cout << "Address of a:\t\t" << &a[0] << endl; 
    cout << "Address of a[2]:\t" << &a[2] << endl; 
    return 0; 
} 

Обратите внимание на адрес . Предполагая, что ваш компьютер использует 32-битные целые числа, вы должны видеть, что адрес a [2] - это просто адрес a + 2 * 4. Причина, по которой он добавляет 2 * 4, а не только 2, состоит в том, что каждое целое число фактически использует 4 байта памяти (т. Е. Одно значение будет охватывать 4 адреса).

Answer 2

int x = a[3]; 

Аппаратное обеспечение делает (адрес а) + (3 * SizeOf (INT))

Это стандартная операция индексации и специализированные аппаратные средства, как правило, доступны, чтобы сделать это в одном шаге.

Answer 3

Если вы пишете что-то вроде этого:

int x = a[3]; 

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

«Начните с адреса памяти: Пройдите 3 адреса памяти вперед. Получите целое число, представленное на этом адресе памяти».

Так что, в принципе, это правда, но это написано таким образом только в образовательных целях. Это не то, что процессор сделал бы в этом случае.

Когда вы получаете доступ к элементу через хэш-таблицу, значение хэша рассчитывается в зависимости от ключа. Многие клавиши могут приводить к одному и тому же значению хэш-функции. Таким образом, должно быть место, где хранятся многие объекты с одинаковыми хэш-значениями, и это место называется ковшом . Поскольку в ведре может быть много объектов, все нужно искать по интересующему вас значению, но все же это гораздо более быстрое решение, чем если бы все значения, хранящиеся в массиве (вам приходилось проходить через все его элементы) ,

Answer 4

Это, по сути, доступ к массиву, это довольно быстро. Хэш-таблицы не быстрее массивов; на самом деле это потому, что они близки так же быстро, как массивы, что они считаются очень быстрыми. Ключевым преимуществом хэш-таблиц является то, что вы можете использовать любой хешируемый тип в качестве ключа, а не целое число. Кроме того, они поддерживают разреженные данные без разрыва пространства впустую массива.

Answer 5

они не более эффективны для доступа, чем массив.

Это не говорит много, потому что массивы ослепляют быстро. Индексирование массива (т. Е. Перехода от одного объекта к случайному другому объекту в этом массиве) - это O (1) - операция с одним добавлением. Большинство процессоров даже имеют специальные инструкции для индексирования в массивы и подобъекты в различных формах, которые могут сделать еще лучше.

Процессор не проходит через каждый адрес по пути - он перескакивает через них, независимо от того, сколько их есть. «Настолько эффективный, как доступ к массиву».