48 비트 키를 16 비트 값으로 해싱

매우 작은 데이터 패킷을받는 장치로 작업하고 있습니다. 장치는 48 비트 키로 고유하게 식별됩니다. 장치가 개별 패킷을 수신하면 패킷을 읽고 해당 패킷이 해당 장치 용인지 여부를 확인해야합니다. 간단하지만, 패킷에는 16 비트 키만 저장할 공간이 충분합니다.48 비트 키를 16 비트 값으로 해싱

통신 프로토콜을 변경할 수 없습니다. 패킷에 여러 패킷이나 다른 필드를 사용할 수 없습니다. 기본적으로이 48 비트 식별자를 16 비트 필드에 저장해야합니다. 분명히 어떤 해결책과도 충돌 할 것입니다.

원본 키의 하위 16 비트를 보내거나 해시하는 것을 고려하고있었습니다. 충돌을 최소화하면서이 작업을 수행하는 가장 좋은 방법은 무엇입니까?

추신 : 실제로 원래의 키의 처음 3 바이트가 항상 같아서이 문제가 24 비트 키를 16 비트 키로 밀어 넣는 것으로 줄었습니다.

PPS : 충돌은 치명적이지 않습니다. 장치는 복구 할 수 있지만 비용이 많이 듭니다.

출처

2013-11-27 vopilif

"충돌을 최소화하면서 이렇게하는 가장 좋은 방법은 무엇입니까?" "사용 된 값의 할당 및 배포에 대해 알지 못하면 대답 할 수 없습니다. – RBarryYoung

개인 키가 임의로 생성되면 해시 키를 사용하여 16 비트 하위 섹션을 가져 오는 것보다 충돌이 적게 발생하지 않습니다. 키가 중요하다면 키를 어둡게하는 것이 좋습니다. –

개별 장치를 프로그래밍 할 수 있습니까? 16 비트 키가 무엇인지 알려주도록 장치를 구성 할 수 있습니까? 모든 장치 ID가 앞에 있다는 것을 안다면 [최소 완벽한 해시]를 만들 수 있습니다 (http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function). 그러나 특정 패킷 번호를 찾기 위해 장치에 알리는 어떤 방법이 없으면 충돌 가능성은 0이 아닙니다. –

이 번호의 생성 패턴을 제조업체에 문의하십시오. 이 24 비트 중 일부는 생산 배치 또는 세계 일부를 식별하여 출하 될 가능성이 매우 높습니다.

요청에 따라 통지없이 언제든지 번호 매기기 정책을 변경할 수 있음을 알고 동의하십시오. 이렇게하면 정보를 제공 할 확률이 높아집니다.

출처

2013-11-27 12:32:39

2^16보다 작거나 같은 장치가있는 경우에만이 상황에서 도움이 될 수 있습니다. 여기에 각 24-bit 키를 고유 한 16-bit 키에 매핑하는 해시 테이블이 있어야합니다. 따라서 패킷을 보내는 동안 16-bit 키를 보내고 검색하는 동안 해시 테이블의 키 매핑 값을 확인하십시오. 직접 비교를 위해 16-bit 키 값을 하드 코딩 할 수도 있습니다. 그러나 2^16 이상의 장치가있는 경우 비둘기 홀 원칙에 따라 동일한 16-bit 키가있는 둘 이상의 장치가 있고 패킷이 의미하는 장치를 확인할 수 없습니다.

의사 코드 & 전송 패킷을 수신 : -

Send(BigKey,Data) { 

    // get 16-bit key from 24-bit one 
    SmallKey = HashMap.getValue(BigKey); 
    Packet = SmallKey + Data ; 

} 

Receive(Packet) { 

    (Key,Data) = split(Packet); 

    // get devices 16-bit key 
    SmallKey = HashMap.getValue(MyKey); 

    if(SmallKey==Key) 
     Process(Data) 
    else Error("Invalid Packet"); 

}

참고 : - 해시 맵이 O (logn)에 조회 않는 등 레드 - 블랙 트리, B- 트리를 사용하여 만들 수 있습니다. 여기에 응용할 수있을 정도로 좋습니다.

출처

2013-11-27 05:51:03

48 비트 키를 16 비트 값으로 해싱

답변

관련 문제