Сюрприз C/C++ структуры (Data structure alignment)

Казалось бы, что размер структуры в C/C++ элементарно равен сумме её частей(прим. лично я так думал).

struct Vector {
 int x;
 int y;
 int z;
};

Большинство скажет: sizeof(Vector) == 3 * sizeof(int) . int как правило равен 4 байтам, т.е. данная структура по идее должна занимать 12 байт. Теоретически - это так. Но (!) практически - как выставите опции компилятора.

Данная "фича" называется "Выравнивание" или "Data Structure Alignment". Она выравнивает размер структуры данных до кратного некоторому числу(естесственно степени 2), например 2, 4, 8. Располагает данные в нужном порядке, а между ними размещает "заполнитель" :) пустоту вобщем.

Для чего это нужно? Здесь описано. Вкратце, это оптимизация данных для ускорения доступа. Как всегда, есть некая точка равновесия между размером данных и скоростью доступа к ним. Короче, должно быть использовано с умом и пониманием.

К каким последствиям это может привести? Последствием может быть неправильное чтение/запись структуры, если оно чётко определено стандартом. Это могут быть различные заголовки файлов, данные и т.д. Такое бы уже не прошло:

read(file, &my_struct, sizeof(my_struct));
write(file, &my_struct, sizeof(my_struct));

Для меня эта новость была неожиданной и привела к нескольким часам выяснения, почему заголовок BMP файла читается неправильно. Оказалось, что IDE Borland Turbo C++ по умолчанию выставлял опцию компилятора - выравнивание в 4 байта.
Вообще заголовок BMP файла должен был занимать 14 байт, но sizeof(BMPHeader) упорно возвращал 16! И из-за этого я никак не мог прочитать смещение до самих данных.
Выставить нужно смещение можно либо выставив опции компилятора, либо директивами:

#pragma pack(push)  /* push current alignment to stack */
#pragma pack(1)     /* set alignment to 1 byte boundary */

/** твоя структура */

#pragma pack(pop)   /* restore original alignment from stack */

p.s.: компилятор borland и IDE Borland TurboC++ используются сугубо по требованию преподавателя.

Ответы на вопросы для собеседования по Java SE (Часть 2)

Продолжаю цикл статей, посвященных ответам на вопросы по Java Core.
Ответы на вопросы для собеседования по Java SE (Часть 1)
Ответы на вопросы для собеседования по Java SE (Часть 3)

Следующие 5 вопросов, тесно связаны с пятеркой предыдущих вопросов, поэтому повторяться не буду. Напишу краткие ответы:

6. Какая связь между hashCode и equals?
Объекты равны, когда equals и hashCode возвращает одни и те же значения. Но необязательно, чтобы два различных объекта возвращали различные хэш коды(такая ситуация называется коллизией).

7. Каким образом реализованы методы hashCode и equals в классе Object?
Реализация метода equals в классе Object сводится к проверке на равенство двух ссылок:

public boolean equals(Object obj) {
  return (this == obj);
}

Реализация же метода hashCode класса Object сделана нативной, т.е. определенной не с помощью Java-кода:
public native int hashCode();
Он обычно возвращает адрес объекта в памяти.

8. Что будет, если переопределить equals не переопределяя hashCode? Какие могут возникнуть проблемы?
Они будут неправильно хранится в контейнерах, использующих хэш коды, таких как HashMap, HashSet.

9. Есть ли какие-либо рекомендации о том, какие поля следует использовать при подсчете hashCode?
Есть. Необходимо использовать уникальные, лучше примитивные поля, такие как id, uuid, например. Причем, если эти поля задействованы при вычислении hashCode, то нужно их задействовать при выполнении equals.
Общий совет: выбирать поля, которые с большой долью вероятности будут различаться.

10. Как вы думаете, будут ли какие-то проблемы, если у объекта, который используется в качестве ключа в hashMap изменится поле, которое участвует в определении hashCode?
Будут. Опять же будут проблемы связанные с хэш коллекциями. А именно, не сможем выбрать элемент из хэш-коллекции, его как будто и не будет.
----

Продолжение следует...

Ответы на вопросы для собеседования по Java SE (Часть 1)

Добрый, предобрый день.
В сети распространены различные варианты вопросов на собеседование по Java SE6. Но ответов на эти вопросы нет. Подумав, я решил, что это очень интересная тема для поста и дальнейшего обсуждения. И поэтому начинается цикл статей, посвященный ответам на вопросы по Java Core. За основу я взял 50 вопросов для интервьюирования.
Итак первые 5 вопросов с моими вариантами ответов:

1. Что такое класс Object? Какие в нем есть методы?
Object это базовый класс для всех остальных объектов в Java. Каждый класс наследуется от Object. Соответственно все классы наследуют методы класса Object.
Методы класса Object:

• public final native Class getClass()
• public native int hashCode()
• public boolean equals(Object obj)
• protected native Object clone() throws CloneNotSupportedException
  
• public String toString()
• public final native void notify()
• public final native void notifyAll()
• public final native void wait(long timeout) throws InterruptedException
• public final void wait(long timeout, int nanos) throws InterruptedException
• public final void wait() throws InterruptedException
• protected void finalize() throws Throwable

Замечание: Для полноты обзора можно сказать, что существует ещё один метод private static native void registerNatives() .

2. Что такое метод equals(). Чем он отличается от операции ==.
Метод equals() обозначает отношение эквивалентности объектов. Эквивалентным называется отношение, которое является симметричным, транзитивным и рефлексивным.

• Рефлексивность: для любого ненулевого x, x.equals(x) вернет true;

• Транзитивность: для любого ненулевого x, y и z, если x.equals(y) и y.eqals(z) вернет true, тогда и x.equals(z) вернет true;

• Симметричность: для любого ненулевого x и y, x.equals(y) должно вернуть true, тогда и только тогда, когда y.equals(x) вернет true.

Также для любого ненулевого x, x.equals(null) должно вернуть false.
Отличия equals() от операции == в классе Object нет. Это видно, если взглянуть исходный код метода equals класса Object:

public boolean equals(Object obj) {
return (this == obj);
}Syhi-подсветка кода

Однако, нужно не забывать, что, если объект ни на что не ссылается(null), то вызов метода equals этого объекта приведет к NullPointerException. Также нужно помнить, что при сравнении объектов оба они могут быть null и операция obj1 == obj2 в данном случае будет true, а вызов equals приведет к исключению NullPointerException.
Как мы видим, при помощи операции == сравниваются ссылки на объекты. Но мы можем переопределять метод equals, тем самым задавая логику сравнения двух объектов. Например, рассмотрим сравнение двух одинаковых чисел, созданных при помощи класса Integer:

Integer a = new Integer(6);
Integer b = new Integer(6);
System.out.println(a == b); // false т.к. это разные объекты с разными ссылками
System.out.println(a.equals(b)); // true, здесь уже задействована логика сравненияSyhi-подсветка кода

Если взглянуть внутрь метода equals класса Integer, то мы увидим:

public boolean equals(Object obj) {
if (obj instanceof Integer) {
return value == ((Integer)obj).intValue();
}
return false;
}Syhi-подсветка кода

Понятно, что тут уже нет сравнения ссылок, а сравниваются int значения.

3. Если вы хотите переопределить equals(), какие условия должны удовлетворяться для переопределенного метода?
Эти условия приведены в пункте 2.

4. Если equals() переопределен, есть ли какие-либо другие методы, которые следует переопределить?
Да, есть.Нужно переопределить метод hashCode(). Равные объекты должны возвращать одинаковые хэш коды. Например у класса Integer метод hashCode() переопределен следующим образом:

public int hashCode() {
return value;
}Syhi-подсветка кодаvalue это private значение, которое хранит объект класса Integer. Собственно это и есть число.

5. Для чего нужен метод hashCode()?
Для начала вспомним, что такое хэш и хэширование. Теперь вспоминаем такие известные классы, как HashMap, HashSet, Hashtable, в основе которых лежит вычисление хэш-функции. Именно за счет хэша мы можем вставлять и получать данные за O(1), то есть за время пропорциональное вычислению хэш-функции.
Например, рассмотрим вставку элементов в HashMap:

public V put(K key, V value) {
...
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
...
addEntry(hash, key, value, i);
...
}Syhi-подсветка кода

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



Пока, что всё. Впереди нас ждет много интересных вопросов!
До встречи.

Продолжение:
Ответы на вопросы для собеседования по Java SE (Часть 2)