#java #hash #copy #time-complexity #heap-memory
#Ява #гашиш #Копировать #временная сложность #кучная память
Вопрос:
Можно ли написать метод foo(x), который не хранит глубокую копию x в переменной экземпляра, где вы можете написать следующее:
Object obj = giveMeSomeObject() // giveMeSomeObject() might return an “atomic” type of object like an Integer or String, // or it might return a Collection, Collection of Collections, etc. FooClass aFooObj = new FooClass(); assert(!aFooObj.foo(obj)); Object clonedObj = obj.deepCopy(); // a hypothetical method that returns a deep copy obj = giveMeSomeObject(); assert(aFooObj.foo(obj) == obj.equals(clonedObj)); На практике foo(x) может сойти с рук хранение хэш-кода x, в зависимости от реализации. Но в принципе, хэш-коды не гарантируют уникальности.
Если есть способ сделать это (то есть сохранить память и время, необходимое для копирования этой памяти), сколько времени займет этот способ по сравнению?
Комментарии:
1. Вы можете просто сохранить ссылку на объект, вам не нужно делать глубокую копию. Я не совсем понимаю, о чем вы спрашиваете.
2. Причина, по которой вы не можете просто сохранить ссылку и проверить наличие идентичных ссылок, заключается в том, что в последнем операторе assert в приведенном выше коде aFooObj.foo(obj) должен возвращать значение true тогда и только тогда, когда первый экземпляр вызова giveMeSomeObject() возвращает объект, который РАВЕН (не идентичен) объекту, возвращенному вторым экземпляром вызова giveMeSomeObject(). Вот что «aFooObj.foo(obj) == obj.равно(clonedObj» утверждает окольным путем.
3. Вы можете использовать хэш-функцию с большим выходом. Для хэш-функции хорошего качества, размер вывода которой равен n битам, вероятность того, что два неравных входа хэшируют один и тот же вывод, составляет около 2**(-n). 128 бит вывода более чем достаточно. Java обеспечивает легкий доступ к крипто-хэшам, которые более чем подходят для этой задачи, но они относительно медленные. Вы можете найти исходный код для более быстрых некриптографических хэшей, которые имеют достаточно большой объем вывода.