3622
правки
Изменения
→Получение элемента по номеру
===Получение элемента по номеру===
Благодаря использованию степеней двойки, мы можем эффективно находить элементы в HAT, используя поразрядные операции. Пусть размер главного массива и каждого листа будет равен <tex>2^{power}</tex>.
'''int''' topIndex('''int''' j):
<font color=green>// Получить номер указателя в основном массиве</font>
'''return''' j >> power
'''int''' leafIndex('''int''' j):
<font color=green>// Получить номер листа</font>
'''return''' j & ((1 << power) - 1)
'''intT''' getHat('''int''' j):
<font color=green>// Вернуть элемент HAT. Нет проверки на выход за пределы массива.</font>
'''return''' top[topIndex(j)][leafIndex(j)]
*Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими.
Рассмотрим как происходит вычисление адреса на примере. Пусть у нас есть HAT с размером листа равным <tex>4</tex>, тогда для нашего случая <tex>power = 2</tex>. Получим значения функций для элемент под номером <tex>5</tex>:
*<tex>topIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен операции деления (взятию по модулю) <tex>j</tex> на <tex>2^{2}</tex>. То есть получим <tex>1</tex> {{---}} действительно элемент под номером <tex>5</tex> находится в первом листе (нумерация листов с <tex>0</tex>).
*<tex>leafIndex(5)</tex> : в данном случае битовый сдвиг эквивалентен умножению <tex>1</tex> на <tex>2^{2}</tex>. То есть после вычитания <tex>1</tex> получим число формата <tex>011..11</tex>, в нашем случае {{---}} <tex>011</tex>. Формула для <tex>leafIndex</tex> справедлива, так как элементы, которые находятся в разных листьях и различаются на <tex>2^k</tex>, будут иметь одинаковую позицию в этих листах, а младшие <tex>k</tex> бит у них будут общими. Поэтому сделаем операцию побивое "и" к запрашиваему индексу и к <tex> 2^k - 1 </tex> и получим нужный индекс в массиве <tex> leaf </tex>.
*<tex>5_{10} = 101_2</tex> , следовательно <tex>101</tex> <tex>\&</tex> <tex>011 = 001</tex>, то есть индекс в листе равен <tex>1</tex> (в листах нумерация тоже с <tex>0</tex>).
