GUID的高效数据结构

Question

我正在寻找一种数据结构,这使我能够快速(优先O(1) - 快速)确定给定的GUID是否是GUID集合的成员.

我目前的方法是使用带有0作为值的TDictionary.

虽然这很快就能起作用,但使用Hashmap来重新定义GUID似乎是一种浪费,GUID通过定义被认为是唯一的,并且使Dictionary处理不需要的值.

必须有一个更好的解决方案,但我找不到一个.你能？

Answer 1

很少有数据结构提供O(1)访问.一个是数组,另一个是哈希地图(大卫的回答),我只知道另一个:特里.下面是一个逐位Trie的简单实现:有一些有趣的属性:

• 免于内存碎片,因为没有重新分配.
• O(1)添加和存在测试.当然,O(1)中涉及的常数相当大.

代码:

program Project23;

{$APPTYPE CONSOLE}

uses
  SysUtils, Generics.Collections;

type

  PGuidTrieNode=^TGuidTrieNode;
  TGuidTrieNode = record
    Sub:array[Boolean] of PGuidTrieNode;
  end;
  TGuidByteArray = array[0..15] of Byte;

  TGuidTrie = class
  protected
    Root: PGuidTrieNode;
  public
    constructor Create;
    destructor Destroy;override;

    procedure Add(G: TGUID);
    function Exists(G: TGUID): Boolean;
  end;

{ TGuidTrie }

procedure TGuidTrie.Add(G: TGUID);
var GBA: TGuidByteArray absolute G;
    Node: PGuidTrieNode;
    i: Integer;
    Bit: Integer;
    IsBitSet: Boolean;
const BitMask: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
begin
  Assert(SizeOf(G) = SizeOf(TGuidByteArray));
  Node := Root;
  for i:=0 to High(GBA) do
  begin
    for Bit := 0 to 7 do
    begin
      IsBitSet := (GBA[i] and BitMask[Bit]) <> 0;
      if (i = High(GBA)) and (Bit = 7) then
        begin
          // Payload
          Node.Sub[IsBitSet] := Pointer(1);
        end
      else
        begin
          if not Assigned(Node.Sub[IsBitSet]) then
            Node.Sub[IsBitSet] := GetMemory(SizeOf(TGuidTrieNode));
          Node := Node.Sub[IsBitSet];
        end;
    end;
  end;
end;

constructor TGuidTrie.Create;
begin
  Root := GetMemory(SizeOf(TGuidTrieNode))
end;

destructor TGuidTrie.Destroy;

  procedure KillNode(Node: PGuidTrieNode);
  var i:Integer;
  begin
    if Assigned(Node.Sub[True]) then
        if Node.Sub[True] <> Pointer(1) then
        begin
          KillNode(Node.Sub[True]);
        end;
    FreeMemory(Node);
  end;

begin
  KillNode(Root);
  inherited;
end;

function TGuidTrie.Exists(G: TGUID): Boolean;
var GBA: TGuidByteArray absolute G;
    Node: PGuidTrieNode;
    i: Integer;
    Bit: Integer;
    IsBitSet: Boolean;
const BitMask: array[0..7] of Byte = (1, 2, 4, 8, 16, 32, 64, 128);
begin
  Assert(SizeOf(G) = SizeOf(TGuidByteArray));
  Node := Root;
  for i:=0 to 15 do
  begin
    for Bit := 0 to 7 do
    begin
      IsBitSet := (GBA[i] and BitMask[Bit]) <> 0;
      if not Assigned(Node.Sub[IsBitSet]) then
      begin
        Result := False;
        Exit;
      end;
      Node := Node.Sub[IsBitSet];
    end;
  end;
  Result := True; // Node now contains the Payload
end;

const G1: TGUID = '{68D09F12-3E0D-4963-B32C-4EE3BD90F69C}';
      G2: TGUID = '{BEED37F6-9757-41DC-8463-AF094392652B}';

var T: TGuidTrie;

begin
  try

    T := TGuidTrie.Create;
    try
      if T.Exists(G1) then WriteLn('Exists')
                      else WriteLn('NOT Exists');
      T.Add(G1);
      if T.Exists(G1) then WriteLn('Exists')
                      else WriteLn('NOT Exists');

      if T.Exists(G2) then WriteLn('Exists')
                      else WriteLn('NOT Exists');
      T.Add(G2);
      if T.Exists(G2) then WriteLn('Exists')
                      else WriteLn('NOT Exists');
    finally T.Free;
    end;

  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

Answer 2

我认为你在99%的路上.

哈希听起来像是正确的解决方案.利用GUID的特殊性质的显而易见的方法是提供自己的散列函数,该函数将构成GUID的4个32位整数组合成单个32位整数.我只是对4个整数进行异或.

我假设您使用的是Generics.Collections.TDictionary.您可以通过将自定义比较器传递给构造函数来提供自己的哈希函数.我不担心存储备用值,我认为它不会以可辨别的方式影响性能.

我相信您将GUID存储为128位整数而不是字符串.

最后,我发现GU​​ID的默认比较器可能确实已经以这种方式生成哈希代码.在进行任何更改之前,值得检查一下.

编辑

默认哈希码使用应用于二进制数据的Bob Jenkins哈希.XOR会更快,但默认的哈希码似乎不会成为性能瓶颈.

换句话说,我认为这TDictionary<TGUID,Integer>将完全满足您的需求.