Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Kyo

how to generate a unique ID for a record?

This topic is 5761 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Just wondering if anyone has a simple algorithm to generate a unique ID for a student record.. I did some searches but what came up was way too complex for my project, I just need something that will take fields like surname, name, date of birth etc... and maybe a random key to generate a unique ID field for that record. For example how do I convert text fields to a numerical value in Visual Basic? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
I gather this is an exercise for school. What is the point of the exercise? Specifically is the point to illistrate hashing? If so the issue isn''t so much how do you generate a hash key as it is how do you resolve collisions, i.e. duplicates. No matter how you hash you can get collisions, but it depends upon how you hash as to how likely that is. A fair exercise should provide you a dataset to test your hashing against.

I believe in Visual Basic ord will give you the ascii code for a character. The simplist thing is to just sum them. I assume you are actually putting this into an Access database so you don''t have to worry about the actual size of the hashing table. You can just generate a number within the size of an integer field. A simple way to handle collision is just attempt to insert what you have. If you have a unique index on the field then an attempt to insert a duplicate fails. So you add one and try again. If you have a dataset then you count how many inserts you attempted and how many rows did you actually insert. The closer the attempts are to the actual the better the algorithm.

Share this post


Link to post
Share on other sites
Here''s what I''ve done, the chances of generating two same ID''s must be pretty small:


  
Public Function generateStudentID(ByVal surname As String, ByVal telNo As String, ByVal collegeID As String, ByVal address As String) As Long
Dim IDString As String ''ID to be returned
Dim randomNum As Integer ''random number forming part of ID
Dim upperBound As Integer ''upper bound of random number
Dim lowerBound As Integer ''lower bound of random number

''generate a random number
upperBound = 999
lowerBound = 1
Randomize
randomNum = Int((upperBound - lowerBound + 1) * Rnd + lowerBound)
IDString = randomNum

''convert string parameters to numbers
IDString = IDString + Right(Str(Asc(surname)), 1)
IDString = IDString + Right(Str(Asc(Mid(telNo, 7, 1))), 1)
IDString = IDString + Right(Str(Asc(collegeID)), 2)
IDString = IDString + Right(Str(Asc(address)), 2)

''return ID as long
generateStudentID = IDString
End Function

Share this post


Link to post
Share on other sites
quote:
Original post by Kyo
Here''s what I''ve done, the chances of generating two same ID''s


With 10.000 students? Really? Think about it and ask your stochastics teacher - VERY bad solution.

Regards

Thomas Tomiczek
THONA Consulting Ltd.
(Microsoft MVP C#/.NET)

Share this post


Link to post
Share on other sites
Scroll down. I believe this is a database application development class using Visual Basic and MS Access. So it seems safe to assume the goal is just to introduce an idea that provides a tool that can be used as the need arrises.

As such the biggest problem I see is sticking the random number in the front. If this was your only index you would need to cut the entire list of students down to just a few given the information you have. The index is stored by key value in order. So missing part at the front of the key is like using a dictionary to find words that end with "tion" as opposed to words that start with "abs".

Also you really don''t need the random number. The goal is something likely to be unique, but you cannot guarantee it even with the random number. So collisions have to be resolved. Where you actually do the insert has to handle the insert failing due to duplicates. It then modifies the number and tries again. Your goal is simply to minimize the number of times you try again.

I would ask your instructor for a list of student names to test against. It is sort of the differance between reading a book on programming and actually writing a program. You need to test your algorithm against real data and see how it works. Since it is a database class you could then split it up into individual letters of the name and the position within the name. Then you can count how many students by letter and position using adhoc queries, i.e. "select letter, position, count(*) from letterbypos group by letter, position". Stick that in another table and select off the sum, max, min and avg by position. You want the highest average with the lowest min where the sum is reasonably close to the number of students. That is a good position to use.

Share this post


Link to post
Share on other sites
I appreciate your help but it''s leaving me with more questions then answers. It''s not specifically a database class we just have to build a system for a user as our project. My teacher isn''t any help.

I''m quite confused about the whole database thing, these are my main questions:

1) An auto-incrementing ID would be unique, why not use that?

2) Why does the ID have to be in an order (no random numbers in front of the ID)? I thought as long as they were unique I could just do SQL queries when I needed to retrieve a student record.

3) If my ID was generated from surname, name, date of birth etc.. Would I have to change the ID everytime a field is edited?

4) Any examples would help greatly googling returned only stuff that''s too advanced.

Bear in mind I haven''t been taught anything on hashing algorithms/generating unique IDs...

Share this post


Link to post
Share on other sites
actually, i just asked a question very similar to this, i needed to get a unique id based on two strings for resource management, so i didn't load anything twice. someone directed me to a CRC32 check, it took 5-10 minutes to make one, i'm trying to find the site that has a prebuilt table. i can't find it again though, but here is my CRC 32 and CRC 16 tables i got off a site:


    [size=2]
static DWORD xCRC32Table[] =
{
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,

0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,

0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,

0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D,
};


static WORD xCRC16Table[] =
{
0x0000, 0xC0C1, 0xC181, 0x0140,
0xC301, 0x03C0, 0x0280, 0xC241,
0xC601, 0x06C0, 0x0780, 0xC741,
0x0500, 0xC5C1, 0xC481, 0x0440,
0xCC01, 0x0CC0, 0x0D80, 0xCD41,
0x0F00, 0xCFC1, 0xCE81, 0x0E40,
0x0A00, 0xCAC1, 0xCB81, 0x0B40,
0xC901, 0x09C0, 0x0880, 0xC841,
0xD801, 0x18C0, 0x1980, 0xD941,
0x1B00, 0xDBC1, 0xDA81, 0x1A40,
0x1E00, 0xDEC1, 0xDF81, 0x1F40,
0xDD01, 0x1DC0, 0x1C80, 0xDC41,
0x1400, 0xD4C1, 0xD581, 0x1540,
0xD701, 0x17C0, 0x1680, 0xD641,
0xD201, 0x12C0, 0x1380, 0xD341,
0x1100, 0xD1C1, 0xD081, 0x1040,

0xF001, 0x30C0, 0x3180, 0xF141,
0x3300, 0xF3C1, 0xF281, 0x3240,
0x3600, 0xF6C1, 0xF781, 0x3740,
0xF501, 0x35C0, 0x3480, 0xF441,
0x3C00, 0xFCC1, 0xFD81, 0x3D40,
0xFF01, 0x3FC0, 0x3E80, 0xFE41,
0xFA01, 0x3AC0, 0x3B80, 0xFB41,
0x3900, 0xF9C1, 0xF881, 0x3840,
0x2800, 0xE8C1, 0xE981, 0x2940,
0xEB01, 0x2BC0, 0x2A80, 0xEA41,
0xEE01, 0x2EC0, 0x2F80, 0xEF41,
0x2D00, 0xEDC1, 0xEC81, 0x2C40,
0xE401, 0x24C0, 0x2580, 0xE541,
0x2700, 0xE7C1, 0xE681, 0x2640,
0x2200, 0xE2C1, 0xE381, 0x2340,
0xE101, 0x21C0, 0x2080, 0xE041,

0xA001, 0x60C0, 0x6180, 0xA141,
0x6300, 0xA3C1, 0xA281, 0x6240,
0x6600, 0xA6C1, 0xA781, 0x6740,
0xA501, 0x65C0, 0x6480, 0xA441,
0x6C00, 0xACC1, 0xAD81, 0x6D40,
0xAF01, 0x6FC0, 0x6E80, 0xAE41,
0xAA01, 0x6AC0, 0x6B80, 0xAB41,
0x6900, 0xA9C1, 0xA881, 0x6840,
0x7800, 0xB8C1, 0xB981, 0x7940,
0xBB01, 0x7BC0, 0x7A80, 0xBA41,
0xBE01, 0x7EC0, 0x7F80, 0xBF41,
0x7D00, 0xBDC1, 0xBC81, 0x7C40,
0xB401, 0x74C0, 0x7580, 0xB541,
0x7700, 0xB7C1, 0xB681, 0x7640,
0x7200, 0xB2C1, 0xB381, 0x7340,
0xB101, 0x71C0, 0x7080, 0xB041,

0x5000, 0x90C1, 0x9181, 0x5140,
0x9301, 0x53C0, 0x5280, 0x9241,
0x9601, 0x56C0, 0x5780, 0x9741,
0x5500, 0x95C1, 0x9481, 0x5440,
0x9C01, 0x5CC0, 0x5D80, 0x9D41,
0x5F00, 0x9FC1, 0x9E81, 0x5E40,
0x5A00, 0x9AC1, 0x9B81, 0x5B40,
0x9901, 0x59C0, 0x5880, 0x9841,
0x8801, 0x48C0, 0x4980, 0x8941,
0x4B00, 0x8BC1, 0x8A81, 0x4A40,
0x4E00, 0x8EC1, 0x8F81, 0x4F40,
0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540,
0x8701, 0x47C0, 0x4680, 0x8641,
0x8201, 0x42C0, 0x4380, 0x8341,
0x4100, 0x81C1, 0x8081, 0x4040,
};
[/size]


[edited by - billybob on February 9, 2003 4:43:14 PM]

[edited by - billybob on February 9, 2003 4:43:37 PM]

[edited by - billybob on February 9, 2003 4:43:52 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Kyo
I appreciate your help but it''s leaving me with more questions then answers. It''s not specifically a database class we just have to build a system for a user as our project. My teacher isn''t any help.

I''m quite confused about the whole database thing, these are my main questions:

1) An auto-incrementing ID would be unique, why not use that?


An auto-incrementing ID would indeed be unique. The only thing you have to worry about is correctly locking it before reading and incrementing it, if there will be concurrent access to the data from multiple threads or processes.

quote:

2) Why does the ID have to be in an order (no random numbers in front of the ID)? I thought as long as they were unique I could just do SQL queries when I needed to retrieve a student record.


You''re right, it doesn''t have to be in order.

quote:
3) If my ID was generated from surname, name, date of birth etc.. Would I have to change the ID everytime a field is edited?


Nah. You shouldn''t try to infer information from the ID number, so as long as it stays unique, there''s no reason to change it. But remember that names may not be unique.

quote:

4) Any examples would help greatly googling returned only stuff that''s too advanced.




int GetUniqueID()
{
static int curID = 0;
return curID++;
}


quote:

Bear in mind I haven''t been taught anything on hashing algorithms/generating unique IDs...


Hashing algorithms have nothing to do with unique IDs. To be sure, good hashing algorithms produce numbers that are as unique as possible, but they are NOT GUARANTEED TO BE UNIQUE. For that matter, all that CRC stuff that billybob was going on about is not unique.

A unique key does not need to encode any information or be helpful at all, other than being unique.


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
MS-Access has a field type that is an unsigned long which auto-increments. you set that up when you create the tables, and each time you add a record it uses the next number. uniqueness is guarenteed unless you manually mess with the numbers, or you go over 4,294,967,296 records.

you can imitate this by starting at 1, and storing the next available number somewhere. when you add a record, use the stored number, and then increment it for next time.

you can usually set a database field to be unique, so it will return an error if you try to use the same number twice (just to be safe).

as for converting text to numbers in VB, the ASC() function returns the ASCII code of a character (i.e. asc("A") = 65). for each character you can get a number between 0-255 (well, probably not, since you will only use letters most likely, which are 65-90 for uppercase, and 97-122 for lowercase), and do some math with those. as people pointed out, though, no math done to those numbers is guarenteed to be unique.

Share this post


Link to post
Share on other sites
quote:
Original post by Kyo
Just wondering if anyone has a simple algorithm to generate a unique ID for a student record.. I did some searches but what came up was way too complex for my project, I just need something that will take fields like surname, name, date of birth etc... and maybe a random key to generate a unique ID field for that record. For example how do I convert text fields to a numerical value in Visual Basic?

Thanks.



The code below uses an API call to generate a GUID.

  
Option Explicit

Declare Function CoCreateGuid Lib "OLE32.DLL" (pGuid As GUID) As Long

Type GUID
Data1 As Long
Data2 As Integer
Data3 As Integer
Data4(7) As Byte
End Type




Function GetGUID() As String


Dim lResult As Long
Dim lguid As GUID
Dim MyguidString As String
Dim MyGuidString1 As String
Dim MyGuidString2 As String
Dim MyGuidString3 As String
Dim DataLen As Integer
Dim StringLen As Integer
Dim i%
Dim cnt As Integer
Dim dt As String
Dim tmp As String
Const S_OK = 0

tmp = ""

On Error GoTo error_olemsg

lResult = CoCreateGuid(lguid)

If lResult = S_OK Then

MyGuidString1 = Hex$(lguid.Data1)
StringLen = Len(MyGuidString1)
DataLen = Len(lguid.Data1)
MyGuidString1 = LeadingZeros(2 * DataLen, StringLen) _
& MyGuidString1 ''First 4 bytes (8 hex digits)

MyGuidString2 = Hex$(lguid.Data2)
StringLen = Len(MyGuidString2)
DataLen = Len(lguid.Data2)
MyGuidString2 = LeadingZeros(2 * DataLen, StringLen) _
& Trim$(MyGuidString2) ''Next 2 bytes (4 hex digits)

MyGuidString3 = Hex$(lguid.Data3)
StringLen = Len(MyGuidString3)
DataLen = Len(lguid.Data3)
MyGuidString3 = LeadingZeros(2 * DataLen, StringLen) _
& Trim$(MyGuidString3) ''Next 2 bytes (4 hex digits)

GetGUID = MyGuidString1 & MyGuidString2 & MyGuidString3

Dim sByte As String

For i% = 0 To 7
sByte = Hex(lguid.Data4(i%))
If Len(sByte) < 2 Then sByte = "
0" & sByte
MyguidString = MyguidString & sByte
Next i%


''MyGuidString contains last 8 bytes of Guid (16 hex digits)
GetGUID = GetGUID & MyguidString

Else
GetGUID = "
00000000" '' return zeros if function unsuccessful
End If

''Convert to hex
For cnt = 1 To Len(GetGUID) Step 2
dt = Mid(GetGUID, cnt, 2)
tmp = tmp & Chr(Val("
&h" & dt))
Next cnt
GetGUID = tmp



Exit Function

error_olemsg:
MsgBox "
Error " & Str(Err) & ": " & Error$(Err)
GetGUID = "
00000000"
Exit Function

End Function


Function LeadingZeros(ExpectedLen As Integer, ActualLen As Integer) As String
LeadingZeros = String$(ExpectedLen - ActualLen, "
0")
End Function


however making a count and setting it to a value like 40,000 then incrementing by one for each student would be a much simpler solution.

Val() converts a string to a number
Str() convert number to string. For example, the value 1 to character 1.

hope this helps

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!