SHA-1 hashing concept in Git - Time & Space Complexity

Time Complexity: SHA-1 hashing concept

O(n)

Understanding Time Complexity

We want to understand how the time to create a SHA-1 hash changes as the size of the data grows.

How does hashing more data affect the work git does?

Scenario Under Consideration

Analyze the time complexity of this git hashing command.

git hash-object <file>
# Internally, git reads the file content
# Then computes the SHA-1 hash of the content
# Finally, it stores the object in the git database

This command creates a SHA-1 hash for a file's content to track it in git.

Identify Repeating Operations

Look for repeated work done during hashing.

• Primary operation: Reading each byte of the file once to process it for hashing.
• How many times: Once per byte, so the number of bytes in the file.

How Execution Grows With Input

As the file size grows, the hashing work grows too.

Input Size (n)	Approx. Operations
10 bytes	About 10 operations
100 bytes	About 100 operations
1000 bytes	About 1000 operations

Pattern observation: The work grows directly with the file size.

Final Time Complexity

Time Complexity: O(n)

This means the time to hash grows in a straight line with the size of the data.

Common Mistake

[X] Wrong: "Hashing always takes the same time no matter the file size."

[OK] Correct: Hashing must look at every byte, so bigger files take more time.

Interview Connect

Understanding how hashing time grows helps you explain performance in version control and data integrity tasks.

Self-Check

"What if git used a different hash algorithm that processes data in fixed-size chunks? How would that affect the time complexity?"

Practice

1. What does the SHA-1 hash in Git uniquely identify?

easy

A. A specific commit or file content

B. The username of the committer

C. The branch name

D. The date and time of the commit

Solution

1. Step 1: Understand SHA-1 purpose in Git

   SHA-1 generates a unique code based on the content of files or commits.

2. Step 2: Identify what SHA-1 represents

   It uniquely identifies the exact content or commit, not metadata like username or branch.

3. Final Answer:

   A specific commit or file content -> Option A

4. Quick Check:

   SHA-1 = unique content ID [OK]

Hint: SHA-1 hashes content, not user or branch info [OK]

Common Mistakes:

• Thinking SHA-1 identifies user info
• Confusing SHA-1 with branch names
• Assuming SHA-1 stores commit date

2. Which command correctly shows the SHA-1 hash of the latest commit in a Git repository?

easy

A. git log -1 --format=%H

B. git sha1sum HEAD

C. git show --hash

D. git commit --hash

Solution

1. Step 1: Recall Git command to show commit hash

   The command 'git log -1 --format=%H' prints the full SHA-1 hash of the latest commit.

2. Step 2: Check other options for correctness

   The other options are invalid or do not exist in Git syntax.

3. Final Answer:

   git log -1 --format=%H -> Option A

4. Quick Check:

   Correct Git syntax for latest commit SHA-1 is git log -1 --format=%H [OK]

Hint: Use git log with format %H for full commit hash [OK]

Common Mistakes:

• Using non-existent git commands
• Confusing commit message commands with hash commands
• Trying to use sha1sum directly on HEAD

3. Given the command git hash-object README.md, what is the expected output?

medium

A. An error because README.md is not a commit

B. The size of README.md in bytes

C. The last commit hash that modified README.md

D. The SHA-1 hash of the README.md file content

Solution

1. Step 1: Understand git hash-object command

   This command computes and outputs the SHA-1 hash of the file content given (README.md here).

2. Step 2: Verify output meaning

   It does not show file size, commit hashes, or errors for valid files.

3. Final Answer:

   The SHA-1 hash of the README.md file content -> Option D

4. Quick Check:

   git hash-object outputs file content SHA-1 [OK]

Hint: git hash-object hashes file content, not commits [OK]

Common Mistakes:

• Expecting commit hash instead of file hash
• Thinking it outputs file size
• Assuming it errors on normal files

4. You run git hash-object -w file.txt but get an error. What is the most likely cause?

medium

A. The -w option is not valid for git hash-object

B. The file.txt does not exist in the current directory

C. You need to commit before hashing

D. The file.txt is already tracked by Git

Solution

1. Step 1: Understand git hash-object -w usage

   The -w option writes the object to Git's object database; it requires the file to exist.

2. Step 2: Identify cause of error

   If file.txt does not exist, the command errors. Other options are incorrect because -w is valid, committing is not required, and tracking status doesn't cause this error.

3. Final Answer:

   The file.txt does not exist in the current directory -> Option B

4. Quick Check:

   Missing file causes git hash-object -w error [OK]

Hint: Check file existence before git hash-object -w [OK]

Common Mistakes:

• Thinking -w is invalid option
• Assuming commit is required before hashing
• Believing tracked files cause this error

5. You want to verify if a file's content matches a specific Git object SHA-1 hash. Which sequence of commands correctly helps you do this?

hard

A. Run git show SHA1_HASH and compare with file.txt content manually

B. Run git diff SHA1_HASH file.txt to see differences

C. Run git hash-object file.txt and compare output with the SHA-1 hash

D. Run git cat-file -p file.txt to get the hash

Solution

1. Step 1: Understand how to get file's SHA-1 hash

   Use 'git hash-object file.txt' to compute the SHA-1 hash of the file content.

2. Step 2: Compare computed hash with given SHA-1

   If the hashes match, the file content matches the Git object.

3. Final Answer:

   Run git hash-object file.txt and compare output with the SHA-1 hash -> Option C

4. Quick Check:

   Compare file hash with SHA-1 using git hash-object [OK]

Hint: Use git hash-object to get file hash for comparison [OK]

Common Mistakes:

• Using git show to compare file content directly
• Trying git diff with SHA-1 hash and file
• Using git cat-file incorrectly on files