none
object.GetHashCode() 질문입니다...

    질문

  • MSDN에서 object.GetHashCode의 기본구현으로는 각 개체에 대한 고유 반환값을 보장하지 않는다고 써있는데
    알고리즘이 중복이 될 수 있게 만들져 있나요?
    아니면 어떠한 특정 상황이 되어야 GetHashCode의 기본구현이 고유값을 반환하지 못하게 되나요?
    2009년 12월 10일 목요일 오전 6:02

모든 응답

  • managed object의 GetHashCode 메서드는 내부적으로 숨겨진 InternalGetHashCode()를 호출하게 되며,
    InternalGetHashCode()는 ObjectNative개체의 GetHashCode 메서드를 호출하게 됩니다.

    public virtual int GetHashCode()
    {
        return InternalGetHashCode(this);
    }

    [MethodImpl(MethodImplOptions.InternalCall)]
    internal static extern int InternalGetHashCode(object obj);


    ObjectNative개체의 GetHashCode 메서드의 구현은 아래와 같습니다.

    FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {
        
        CONTRACTL
        {
            THROWS;
            DISABLED(GC_NOTRIGGER);
            INJECT_FAULT(FCThrow(kOutOfMemoryException););
            MODE_COOPERATIVE;
            SO_TOLERANT;
        }
        CONTRACTL_END;

        VALIDATEOBJECTREF(obj);
        
        DWORD idx = 0;
        
        if (obj == 0)
            return 0;
        
        OBJECTREF objRef(obj);

        HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);

            
        idx = GetHashCodeEx(OBJECTREFToObject(objRef));

        
        HELPER_METHOD_FRAME_END();

        return idx;
    }
    FCIMPLEND

    INT32 ObjectNative::GetHashCodeEx(Object *objRef)
    {
        CONTRACTL
        {
            MODE_COOPERATIVE;
            THROWS;
            GC_NOTRIGGER;
            SO_TOLERANT;
        }
        CONTRACTL_END

        VALIDATEOBJECTREF(objRef);

        DWORD iter = 0;
        while (true)
        {
            DWORD bits = objRef->GetHeader()->GetBits();

            if (bits & BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX)
            {
                if (bits & BIT_SBLK_IS_HASHCODE)
                {
                    return  bits & MASK_HASHCODE;
                }
                else
                {
                    SyncBlock *psb = objRef->GetSyncBlock();
                    DWORD hashCode = psb->GetHashCode();
                    if (hashCode != 0)
                        return  hashCode;

                    hashCode = Object::ComputeHashCode();

                    return psb->SetHashCode(hashCode);
                }
            }
            else
            {
                if ((bits & (SBLK_MASK_LOCK_THREADID | (SBLK_MASK_APPDOMAININDEX << SBLK_APPDOMAIN_SHIFT))) != 0)
                {
                    objRef->GetSyncBlock();
                }
                else
                {
                    if (bits & BIT_SBLK_SPIN_LOCK)
                    {
                        iter++;
                        if ((iter % 1024) != 0 && g_SystemInfo.dwNumberOfProcessors > 1)
                        {
                            YieldProcessor();
                        }
                        else
                        {
                            __SwitchToThread(0);
                        }
                        continue;
                    }

                    DWORD hashCode = Object::ComputeHashCode();

                    DWORD newBits = bits | BIT_SBLK_IS_HASH_OR_SYNCBLKINDEX | BIT_SBLK_IS_HASHCODE | hashCode;

                    if (objRef->GetHeader()->SetBits(newBits, bits) == bits)
                        return hashCode;
                }
            }
        }
    }

    말 그대로 닷넷 object 개체의 기본 GetHashCode 메서드는 위 로직에 의거하여 100% 유니크한 해쉬코드를 장담하지 못한다는 겁니다.
    그것은 특정 상황일 수도, 아닐 수 도 있습니다. 우연치 않게 같은 값을 유발할 가능성이 있다는 것이겠죠.

    예를 하나 들겠습니다. 제가 만든 클래스에 메모리 주소값과 객체의 상태값을 조합하여 해쉬코드를 반환하는 GetHashCode메서드를 재정의 했다고 칩시다. 두 객체를 생성하고 각각 다른 상태값이 주어졌다면, 두 객체는 주소값도 다를 것이며 상태값도 다를것입니다. 이렇게 조합된 해쉬코드도 다를것이라 생각되지만 우연히라도 해쉬코드가 같을 수도 있겠죠. 좀더 복잡한 알고리즘을 쓴다면 그 확률은 최대한 피해갈 수는 있겠습니다.

    String 개체의 재정의된 GetHashCode() 구현을 들여다 보겠습니다.

    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
    public override unsafe int GetHashCode()
    {
        fixed (char* str = ((char*) this))
        {
            char* chPtr = str;
            int num = 0x15051505;
            int num2 = num;
            int* numPtr = (int*) chPtr;
            for (int i = this.Length; i > 0; i -= 4)
            {
                num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
                if (i <= 2)
                {
                    break;
                }
                num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
                numPtr += 2;
            }
            return (num + (num2 * 0x5d588b65));
        }
    }

    이 경우는 결국 객체의 상태값만을 가지고 해쉬코드를 생성하고 있기 때문에 인스턴스가 달라도 값이 같으면 같은 해쉬코드를 반환하게 됩니다.

    GetHashCode 메서드는 Equals 동작에 영향을 주기 때문에 GetHashCode를 재정의 할 시 Equals 도 재정의 해 주셔야 합니다.
    이것과 관련된 내용은 MSDN에 이미 잘 나와 있으니 그것을 참조하시기 바랍니다.

    감사합니다.
    • 답변으로 제안됨 Jinsu Han 2009년 12월 18일 금요일 오후 4:38
    2009년 12월 16일 수요일 오전 4:17
  • hash는 말그대로 원래 값을 어떤 특정 값으로 축소해 주는 겁니다. 용도는 여러가지 겠지만 가장 흔한 것중 하나는 객체들의 equality를 체크 할때 비교할 객체의 숫자를 줄여 주는것이지요.

    쉽게 생각해서, hashcode가 32비트라고 한다면, 그럼 hashcode가 나타낼수 있는 unique한 객체의 수는 2^32이고 만약 내가 가지고 있는 객체의 수가 2^32보다 많을 경우 당연히 어떤 두 객체는 같은 hashcode를 공유 할수 밖에 없겠지요.

    만약 내가 이 2^32의 객체중 동일한 객체들을 찾아야 할시, 이 모든 객체를 다 비교 하는것 보단, 그중 같은 hashcode를 가진 것들만 찾아서 equality 체크 하는게 훨신 효과적일테죠.

    하여간 간단히 말해서 hashcode는 unique한 키로 사용 하기 위한 개념이 아닙니다. 본인이 GetHashCode를 구현할때 unique한 값을 사용하도록 하실수도 있겠지만, 그건 implementation detail일 뿐이고, hashcode의 본래 용도는 아닙니다. 본인이 암묵적으로 hashcode를 다른 목적으로 사용하시는 것이지요. 권장 하지 않는 방법이고, 만약 unique한 키고 필요할시 본인이 GetUniqueKey 같은 method를 만드시기 바랍니다.

    수고.

     


    HeeJae Chang
    2010년 11월 2일 화요일 오전 10:47